Chapter 2 形式语言与自动机基础

真TMD气死老子了，考这个b编译原理期中，其他题一分没扣，就这b自动机两个大题几乎分扣完了，CTMD，SB自动机，编译原理你考自动机还考两个是吧，害老子白丢2分总分，正则文法有你这么诡异的吗？？？你看看往年题呢？？

自动机是非常好的发明，在编译原理中有重要作用，我们一定要学好自动机理论

「大水课」の复习

与这学期有关的自动机理论减少到了正则文法和有限自动机，而且考试还考的是确定有限自动机DFA。

分清0型、1型、2型、3型。

2型是CFG，3型是「正规文法」「线性文法」，所产生的语言叫「正规语言」

所以我们一定要上正规大学

其实正则和正规是一个意思

正规文法在所有产生式的右侧，最多只有一个非终结符，并且如果存在，它必须出现在最右端。

至于左线性文法，构造出的DFA是镜像的，我们不管它。

自顶向下的语法分析不能识别左递归文法

预测分析法不能识别左公因子文法，在填预测分析表时会出现多重表项 总之，消除左递归和提取左公因子只有改写为LL(1)文法时才需要！！

实际上主要考右线性文法与确定有限自动机(DFA)的等价性

定理2.3 对每一个右线性文法G或左线性文法G，都存在一个等价的有限自动机M

定理2.4 对每一个DFA M，对存在一个等价的右线性文法G和一个等价的左线性文法G'

推论2 对任何一个有限自动机M，对存在一个等价的正规文法G，反之亦然

推论3 对任何一个右线性文法G，都存在一个等价的左线性文法G’，反之亦然

右线性文法 -> 有限自动机（不一定是DFA）：这是非常简单的，因为只管将B->aB写成$\delta(B,a) = {B}$就行了，注意只有终结符的对应终结状态。但这不一定是确定的！！！

有限自动机（不一定是DFA）-> 右线性文法 ：

原题给出的自动机

按左侧写法空串消不完全就导致了B状态少识别一个0?是这个原因吗？一点也不直观，操

期中第二题

有限自动机 -> 正规表达式：

正规表达式 -> 有限自动机：

正规表达式 -> 正规文法：

正规文法 -> 正规表达式：