简单文法与有限状态机

文法 Grammar

文法是形式化的语言规则， 因此文法是用于生成语言，而语言依托于词，或者说语言是词的组织，因此一个文法所能产生的语言依赖于词的集合，词的拼接组成了句，句构成了语言，因此可以认为，词是句的子集，句是语言的子集，有些词或者句在一些条件（或无条件下）能被进一步替换，而描述这些替换规则的式子就称为产生式 production，因此给出文法G的定义
$$G=(V,T,S,P)$$
其中V表示一个文法所使用的词的集合

T表示不能被进一步替换的词的集合，称为终结符 terminator

S表示生成一个语言的初始词

P表示产生式 production的集合，表示词或句的替换规则

并且一个文法G所能生成的语言L(G)
L ( G ) ⊂ V ∗ , ∗   是   K l e e n e 闭 包 ， 即 字 符 拼 接 运 算 其 中   V 0 = { λ } V i 表 示 进 行 i 次 拼 接 ， 每 次 选 取 V 中 的 一 个 元 素 L(G)\subset V^*, *\ 是\ Kleene闭包，即字符拼接运算\\ 其中\ V^0=\{\lambda\}\\ V^i表示进行i次拼接，每次选取V中的一个元素 L(G)⊂V∗,∗ 是 Kleene闭包，即字符拼接运算其中 V0={ λ}Vi表示进行i次拼接，每次选取V中的一个元素

当我们在讨论文法 Grammar的时候，我们考虑的是语言的合法性，此时我们不关心语言的语义，即我们在做语法分析

我们提到词或句在一些条件下能被进一步替换，乔姆斯基将文法依据特定的条件分为四类

文法类型	名称	对应的有限状态机
0	无约束条件文法	图灵机
1	上下文有关文法	线性有界自动机
2	上下文无关文法	下推自动机
3	正则文法	有限状态自动机

$$\begin{gathered} 下面使用大写字母表示非终结符，小写字母表示词和句 \\ (i)lAr\to lwr \\ orS\to \lambda \\ (ii)A\to w \\ (iii)A\to aB|a \\ orS\to \lambda \end{gathered}$$

有限状态机 automaton

有限状态机的基本功能是描述状态转移的机器，因此需要一个状态转移方程，该方程需要一个基本的参数s，即现态，加上输入i，产生次态。同时可以考虑在发生状态转移时是否伴随有输出，是否存在停机状态，是否能存储输出

语言识别

如果一个有限状态机能识别一种语言，当且仅当该有限状态机能处理该语言并停机

确定性

表示有限状态机的状态转移方程是否是函数，若是函数，则是确定状态机，否则是非确定状态机，非确定状态机在发生状态转移时会在多个转移规则中选择一个

有限状态自动机

给出有限状态自动机的描述
$$M=(S,I,f,F)$$
其中S表示状态集

I表示输入的符号集

f表示状态转移方程

F表示终结状态集

该自动机无存储器，并且伴随状态转移无输出，且处理正则语言

正则表达式

形如下式的是正则表达式
$$\begin{gathered} (i)\varnothing \\ (ii)\lambda \\ (iii)x\in I \\ (iiii)递归定义当A，B是正则式时， \\ AB(表示集合的连接？),A\bigcup B,A^{\ast }（Kleene\ast ）也都是正则式 \end{gathered}$$

正则集合

一个集合是正则集合当且仅当其所有元素都是正则式

Kleene定理

一个集合是正则的当且仅当它能被一个有限状态自动机识别

下推自动机

下推自动机在有限状态自动机的基础上加上了一个栈用来存储信息

线性有界自动机

线性有界自动机以条带存储信息，并且该存储器条带是有限长度的

图灵机

最强大的计算模型图灵机，包含无限长的存储条带

几种自动机等价于文法类型的证明看不懂…

NP问题

可计算

一个问题如果能由图灵机计算，那么就叫做可计算问题

P

表示一个问题可在多项式时间被计算出来

NP

表示可以在多项式时间内判定一个解是否是该问题的解，显然P问题包含于NP问题

NPC

最大范围的NP问题，即所有的NP问题是其子集

NP=P

因为所有NP问题的是NPC问题的子集，如果能针对NPC问题找出一个多项式时间内的通解，那么即对所有的NP问题，都存在一个多项式时间内的解，即NP=P