右线性文法和有限自动机
目录有限状态系统的概念
状态：状态是可以将事物区分开的一种标识
离散状态系统：状态数有限，不能连续变化
连续状态系统：状态可以连续变化，状态数无限
有限状态系统必然是离散状态系统
有限自动机的概念
- 具有离散输入输出的系统的一种数学模型（可以没有输入和输出）
- 有限的状态
- 状态 + 输入 -> 状态转移
- 确定有限状态自动机（DFA）：在特定输入下，每次转换的后继状态唯一
- 不确定有限状态自动机（NFA）：在特定输入下，每次转换的后继状态不唯一
有限自动机的五要素
- 有限状态集
- 有限输入符号集
- 转移函数
- 开始状态
- 终态集合
确定有限自动机
DFA 的形式定义
DFA 是一个五元组\(M=(Q,T,\delta,q_0,F)\)
- Q：有限的状态集合
- T：有限的输入字母表
- \(\delta\)：转换函数
- \(q_0\in Q\)：初始状态
- \(F\subseteq Q\)：终止状态集
扩展转移函数适合于输入字符串
\(\delta':Q \times T \to Q\)
对于\(\forall q\in Q\)，有
- \(\delta'(q,\epsilon)=q\)
- w 是字符串，a是字符，\(\delta'(q,wa)=\delta(\delta'(q,w),a)\)
DFA 接受的语言
- DFA 接受的字符串：输入结束后使 DFA 到达终止状态的字符串
- DFA 接受的语言：被 DFA 接受的字符串的集合
- \(L(A)=\{w|\delta'(q_0,w)\in F\}\)
格局：描述有限自动机某一个时刻的工作状态
- 由当前状态 q 和待输入字符串 w 构成
- 初始格局：\((q_0,w)\)
- 终止格局：\((q,\epsilon),q\in F\)
不确定有限自动机
NFA 的形式定义：后继状态是 Q 的子集，其余和 DFA 一样
NFA 接受的字符串：接收一个字符串后 NFA 进入的状态集包含一个或以上的终止状态，则 NFA 接受该字符串
NFA 的状态转移函数扩展
- \(\delta'(q,\epsilon)={q}\) 空串状态不变
- \(\delta'(q,wa)=\{p|\exist r \in \delta'(q,w)\cap p\in \delta(r,a)\}\)
- 含义：\(\delta'(q,wa)\) 对应的状态集合是 \(\delta'(q,w)\) 对应的状态集合的每一个状态再接收字符 a 后到达的状态集合的并集
NFA 接受的语言：\(L(A)=\{w|\delta'(q_0,w)\cap F\neq \phi \}\)
NFA 和 DFA 的等价性
显然，DFA 可以看作是 NFA 的特例（状态子集只含有一个状态）
所以只需证明 NFA 可以转化成 DFA
定理：$\forall NFA 接受语言 L,\exist DFA 接受语言 L $
证明：子集构造法
\[某个NFA\quad M_N=(Q,T,\delta,q_0,F)，构造 DFA\quad M_D=(Q_D,T,\delta_D,q_0,F_D)\\ Q_D=2^Q\quad 即把原有状态集合的幂集作为新的状态集合\\ \] 标签：状态,文法,第三章,NFA,有限,delta,自动机,DFA From： https://www.cnblogs.com/DrinkLessMilkTea/p/18065399