开启形式言语与自动机的复习啦！！知识点比较少，但是推理证明比较多，就直接参考以前的笔记📒迅速回顾一下好了
Reference：HIT 王春宇 Mooc, MIT Sisper
第一部份
这一部份主要讲字符串的一些运算规则，相关的证明方法，DFA还有NFA。
DFA(Deterministic Finite Automaton)是由五元组(状态集，字母表，转移函数，初始状态，接受状态)构成的，理解它的运行过程就类比一条纸带和一个读头，每一次的转移必须明确且不会卡住，这是DFA的特点。状态转移表(state diagram)注意用-->标注开始状态，*标注接受状态。扩展转移函数要熟悉证明。
NFA(Nondeterministic Finite Automaton)由同样的五元组构成，不过转移函数是到跳转到一个状态集（幂集，因为跳转是非确定的），接受状态也是一个状态集，识别字符串过程注意看图⚠️。状态转移表是一个幂集！！接受只要当前状态和接受状态集有交集即可。
DFA与NFA的等价性证明：用NFA构造DFA，然后用归纳假设法证明(具体证明过程多理解)
epsilon-NFA:在NFA基础上允许用空串epsilon跳转⏭️，五元组相对NFA在转移函数多了一个空串的转移。epsilon-NFA(要消除空转移)与DFA的等价性证明也是子集构造法。显然，任何DFA都是epsilon-NFA。
以上三种自动机都是等价的！！！！
A language is called a regular language if some finite automaton recognises it.
第二部分
正则表达式(Regular expression):通过表达式描述正则语言,相关运算可以直观理解。
DFA，NFA，epsilon-NFA，正则表达式在表示语言的能力上等价。（等价性归纳证明！）
化简规则可以直观理解
状态消除法：先分别在首尾添加开始和结束的状态，然后逐步化简，注意要把去掉的路径补齐全
正则表达式代数定律，结合律，分配律满足；交换律肯定不满足。
判断正则表达式是否等价：可以将变量替换为具体表达式，带进去检验（仅仅限于判断！）
正则语言的泵引理(pumping lemma):只能用来证伪因为泵引理只是正则语言的必要条件，将串w（长度>=N）分成3部份xyz，其中xy长度<=N,y用来泵出新串,然后检查xy^k是否可以被正则语言接受。泵引理的证明多看图回顾。正则语言没有记忆性，仅通过这个就可以判断大部份正则语言。
正则语言的封闭性：并、连接、闭包、补、差、交、反转、同态、逆同态运算下封闭（差的求法是画状态图然后取反就行，证明可以用逻辑运算），（交运算证明用德摩根律）。
状态等价：两个状态经过同样的字符串输入后都可以被接受则等价，反之。（不一定是相同状态）
DFA最小化：填表算法根据例题来记忆，把等价的状态集分成块，构造最小化DFA（这个方法感觉不是很有用的样子），其实可以采取手动迭代的方式，第一步把接受状态和非接受状态区分开来，然后根据输入字符进行进一步区分（参考2018年东工情工题目）
第三部份
上下文无关文法(CFG,Context-Free Grammar),是一个四元组（变元的有穷集，终结符有穷集，产生式有穷集，文法开始的初始符号）
派生(Derivation)：自顶向下，由产生式的头向体分析,进行扩展。
归约(Reduction)：自底向上，对表达式进行简化。
上下文无关语言(Context-Free Language):是由CFG定义的语言。
语法分析树(Parse Tree)：和派生过程等价；每棵语法分析树都有唯一的最左(右)派生。如果CFG G使某些符号串有两棵不同的语法分析树，则称文法G是有歧义的(ambiguous)，“判定任何给定的CFG G是否歧义”是一个不可判定问题（没有一个有限步骤内的算法，涉及到无限的字符检验）
文法化简：1️⃣消除epsilon产生式 2️⃣消除单元产生式 3️⃣消除非产生的无用符号 4️⃣消除非可达的无用符号
乔姆斯基范式(CNF,Chomsky Normal Form)：A-->BC和A-->a这样的形式
格雷巴赫范式(GNF,Greibach Normal Form)：A-->a⍺，⍺是零个或多个变元的串
下推自动机(PDA,Pushdown Automata)：理解为一个读头进行压栈弹栈，由七元组构成(有穷状态集，有穷输入符号集，有穷栈符号集，状态转移函数，初始状态，栈底符号，接受状态集),转移规则是：读入的符号，当前栈顶X/更为当前栈顶为Y。与CNF，GNF等价。
上下文无关语言的泵引理(pumping lemma for CFL):CNF格式的CFG画出语法分析树，然后派生.....Z = uvwxy,其中 vwx长度<= N;vx均不能为🈳,且用来泵出新串。CFL同样用来证伪。
CFL对并/连接/闭包/反转/同态/逆同态封闭，对交和补运算不封闭（列举反例）
CFL和正则语言的交还是CFL，这是一个很容易忽略的性质！！！
CYK算法：由下至山，参考例题复习
完结散花🎉参考修考过去问进行查漏补缺