计算模型
DFA（确定性有限状态自动机）
一个 DFA 被如下五元组定义 \((Q,\Sigma,\delta,q_0,F)\)，
- \(Q\) 是状态集
- \(\Sigma\) 是输入字符集
- \(\delta : Q \times \Sigma\to Q\) 是转移函数
- \(q_0\) 是起始状态
- \(F\subseteq Q\) 是接受状态集
NFA（非确定性有限状态自动机）
一个 NFA 被如下五元组定义 \((Q,\Sigma,\delta,q_0,F)\)，
- \(Q\) 是状态集
- \(\Sigma\) 是字符集（\(\Sigma_\varepsilon=\Sigma\cup\{\varepsilon\}\)）
- \(\delta:Q\times \Sigma_\varepsilon\to \mathcal P(Q)\)
- \(F\subseteq Q\)
language（语言）
定义：设有一个集合，是 \(M\)（ \(M\) 不一定是自动机）可以接受的所有字符串，那么 \(A\) 被称为 \(M\) 的语言（也可以说 \(M\) 识别 \(A\) 或 \(M\) 接受 \(A\)）
regular language（正则语言）
一个语言被称为正则语言如果有某个有限状态自动机识别它
对于正则语言 \(A,B\)，\(A\cup B\)，\(A\cap B\)，\(A^c=\{\omega\mid \omega\not \in A\}\) 和 \(A^*=\{x_1x_2\dots x_k\mid k\in \mathbb N,x_i\in A\}\) 也是正则语言
NFA vs DFA
一样强。
NFA 不弱于 DFA 是显然的，而将 NFA 定义扩展到 \(\mathcal P(Q)\) 上即可证明 NFA 可以转成 DFA
regular expression（正则表达式）
\(R\) 被称为正则表达式如果：
(1) \(a\)（单个字符）
(2) \(\varepsilon\)（可匹配任意字符）
(3) \(\emptyset\)（空集）
(4) \(R_1\cup R_2\)
\((5)\) \(R_1\circ R_2\)（拼接）
\((6)\) \(R_1^*\)
regular expression vs regular languages
一个语言是正则的当且仅当存在正则表达式描述它
通过正则表达式的构造方式可以构造出自动机
而根据 DFA，也能得到一个正则表达式，具体算法如下：
设 \(R_k(u,v)\) 表示从 \(u\) 到 \(v\)，经过 \(k\) 轮的正则表达式，第 \(k\) 轮枚举所有 \(u\) 和 \(v\)，令
\[R_k(u,v)=R_{k-1}(u,v)\cup\left(R_{k-1}(u,k)\circ R_{k-1}(k,k)^*\circ R_{k,v}\right) \]\(n=|Q|\) 轮后得到 \(R_n(u,v)\) 表示从 \(u\) 到 \(v\) 的正则表达式，最后将每个从 \(q_0\) 到 \(q\in F\) 的正则表达式去并即得该 DFA 的正则表达式
pumping lemma
如果 \(A\) 是正则语言，那么存在一个整数 \(p\)，如果 \(s\in A\) 的长度 \(\ge p\)，那么 \(s\) 可以被切分成 3 段 \(s=xyz\) 满足：
(1) \(xy^iz\in A\)，对于 \(i=0,1,\dots\)
(2) \(|y|>0\)
(3) \(|xy|\le p\)
证明：\(A\) 是正则语言，根据正则语言的定义说明存在 DFA 接受 \(A\)，设 \(p=|Q|+1\)，任意长度 \(\ge p\) 的必然走出了环，然后令 \(y\) 为最后一个经过的环形成的串，即证
context free languages(CFL)（上下文无关语言）
一个 context free grammar（上下文无关文法）被四元组 \((V,\Sigma,R,S)\) 定义：
(1) \(V\) 是变元有穷集合
(2) \(\Sigma\) 是符号的有穷集合，构成了被定义语言的串，被称为终结符或终结符号
(3)一个产生式（或规则）的有穷集合 \(R\)，用来表示语言的递归定义，将一个变元替换成一个含有变元和终结符号的串
(4)起始状态 \(S\)
经过一些转化，存在一个等价的 \(CFG\)，满足所有规则都形如：
(1) \(A\to BC\)
(2) \(A\to a\)
称为乔姆斯基范式
pushdown automata(PDA)（下推自动机）
一个 PDA 被如下六元组定义 \((Q,\Sigma,\Gamma,\delta,q_0,F)\)，其中 \(Q,\Sigma,\Gamma,F\) 都是有限集并且
(1) \(Q\) 是状态集合
(2) \(\Sigma\) 是字符集
(3) \(\Gamma\) 是堆栈符号
(4) \(\delta:Q\times \Sigma_\varepsilon\times \Gamma_\varepsilon\to \mathcal P(Q\times \Gamma_\varepsilon)\) 是转移函数（取到 \(\varepsilon\in \Gamma_\varepsilon\) 表示弹栈）
(5) \(q_0\in Q\) 是起始状态
(6) \(F\subseteq Q\) 是接受状态集
from grammer to PDA
遇到变元就压栈，模拟即可
from PDA to grammer
PDA 每轮相当于栈顶符号加某个输入，转化为堆栈符号串
pumpling lemma for CFLs
如果 \(A\) 是 \(CFLs\)，那么存在一个整数 \(p\)，如果 \(s\in A\) 的长度 \(\ge p\)，那么 \(s\) 可以被切分成 5 段 \(s=uvxyz\)，满足：
(1) \(uv^ixy^iz\in A\)
(2) \(|vy|>0\)
(3) \(|vxy|\le p\)
不妨设 \(CFG\) 是乔姆斯基范式，如果 \(s\) 足够长，必然有变元重复，去最后一个重复的变元，\(s\) 可以展开成一个树结构，其中 \(x\) 形成的串是 \(vxy\) 的子树，并且这两个是由同一个变元展开的，将 \(x\) 替换为 \(vxy\) 也是在 \(A\) 中的，因此 (1) 成立，(2) 显然成立，(3) 是因为是最后一个重复的变元
DTM(Deterministic Turing Machine)（确定性图灵机）
一个 \(k\)-tape TM 被如下七元组定义 \((Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})\)
\(Q\) 是状态集，\(\Sigma\) 是输入字符集，\(\Gamma\) 是纸带字符集
\(\delta:Q\times \Gamma^k\to Q\times \Gamma^k\times \{L,S,R\}^k\)
\(q_0\) 是起始状态，\(q_{accept}\) 是接受状态，\(q_{reject}\) 是拒绝状态
对于一个输入，有三种结果，接受，拒绝，死循环
\(M\) 的语言是 \(\{\omega \mid M\ accepts\ \omega\}\)
recognize vs decidable
一个语言是可识别的，如果存在某个图灵机识别它，即在这些输入上结果为接受
如果一个图灵机 \(M\) 在任意输入上都停机，称 \(M\) 为 decider，如果 \(M\) 是 decider，称 \(M\) decides（判定） \(L(M)\)
一个语言是 Turing-decidable 的，如果存在 \(M\) 判定这个语言
标签：varepsilon,语言,理论,导论,times,计算,delta,Sigma,Gamma From： https://www.cnblogs.com/xay5421/p/18257723