形式语言与自动机理论电子教案02.pptVIP

* * 2.5 空语句 由于S不出现在G的任何产生式的右部，所以，如果L(G)中存在长度非0的句子，S?ε不可能出现在它们的推导中。也就是说，将S?ε从G中去掉后，不会影响L(G)中任何长度非0的句子的推导。容易证明： L(G′)=L(G)-{ε} 由于G′是CSG，所以，L(G)-{ε}是CSL。 同理可证其他两个命题。 * * 2.5 空语句 对于任意文法G=(V，T，P，S)，对于G中的其他变量A，出现形如A?ε的产生式是不会改变文法产生的语言的类型的，而且这样一来，对我们进行文法的构造等工作还提供了很多方便。所以，我们约定：对于G中的任何变量A，在需要的时候，可以出现形如A?ε的产生式。 * * 2.6 小结 本章讨论了语言的文法描述。首先介绍文法的基本定义和推导、归约、文法定义的语言、句子、句型、文法的等价等重要概念。讨论了如何根据语言的特点、通过用语法变量去表示适当的集合（语法范畴）的方法进行文法构造，并按照乔姆斯基体系，将文法划分成PSG、CSG、CFG、RG等4类。在这些文法中，线性文法是一类重要的文法。 * * 2.6 小结 ⑴ 文法G=(V，T，P，S)。任意A∈V表示集合L(A)={w | w∈T*且A ?* w}。 ⑵ 推导与归约。文法中的推导是根据文法的产生式进行的。如果α?β∈P，γ，δ∈(V∪T)*，则称γαδ在G中直接推导出γβδ：γαδ?G γβδ；也称γβδ在文法G中直接归约成γαδ。 * * 2.6 小结 ⑶ 语言、句子和句型。文法G产生的语言L(G)={w | w∈T*且S ?* w}，w∈L(G)为句子。一般地，由开始符号推出来的任意符号行叫做G的句型。 ⑷ 一个语言可以被多个文法产生，产生相同语言的文法被称是等价的。 * * 2.6 小结 ⑸ 右线性文法的产生式都可以是形如A?a和A?aB的产生式。左线性文法的产生式都可以是形如A?a和A?Ba的产生式。左线性文法与右线性文法是等价的。然而，左线性文法的产生式与右线性文法的产生式混用所得到的文法不是正则文法。 * * 文法的乔姆斯基体系 定理 2-1 L是RL的充要条件是存在一个文法，该文法产生语言L，并且它的产生式要么是形如：A?a的产生式，要么是形如A?aB的产生式。其中A、B为语法变量，a为终极符号。 证明 ： 充分性：设有G′，L(G′)=L，且G′的产生式的形式满足定理要求。这种文法就是RG。所以，G′产生的语言就是RL，故L是RL。 * * 文法的乔姆斯基体系 必要性 构造：用产生式组： A?a1A1 A1?a2A2 … An-1?an 代替产生式 A? a1a2…an * * 文法的乔姆斯基体系 用产生式组 A?a1A1 A1?a2A2 … An-1?anB 代替产生式 A? a1a2…an B * * 文法的乔姆斯基体系 证明L(G′)=L(G) 。 施归纳于推导的步数，证明一个更一般的结论：对于?A∈V，A ?G+ x?A? G′+ x。因为S∈V，所以结论自然对S成立。 * * 文法的乔姆斯基体系 几点注意事项 ⑴ 我们是按照RG的一般定义来构造一个与之等价的文法的，这与读者以前熟悉的根据一个具体的对象构造另一个对象是不同的。在这里，可以使用的是非常一般的条件——一个一般模型。这也是这类问题的证明所要求的。而且在本书的后面，将会有更多这样的情况。 * * 文法的乔姆斯基体系 ⑵ 为了证明一个特殊的结论，可以通过证明一个更为一般的结论来完成。这从表面上好像是增加了我们要证明的内容，但实际上它会使我们能够更好地使用归纳假设，以便顺利地获得我们所需要的结论。 * * 文法的乔姆斯基体系 ⑶ 施归纳于推导的步数是证明本书中不少问题的较为有效的途径。有时我们还会对字符串的长度施归纳。 本证明的主要部分含两个方面，首先是构造，然后对构造的正确性进行证明。这种等价性证明的思路是非常重要的。 * * 文法的乔姆斯基体系 线性文法(liner grammar) 设G=(V，T，P，S)，如果对于?α?β∈P，α?β均具有如下形式： A?w A?wBx 其中A，B∈V，w，x∈T*，则称G为线性文法。 线性语言(liner language) L(G)叫做线性语言 * * 文法的乔姆斯基体系 右线性文法(right liner grammar) 设G=(V，T，P，S)，如果对于?α?β∈P，α?β均具有如下形式： A?w A?wB 其中A，B∈V，w，x∈T*，则称G为线性文法。 右线性语言(right liner language) L(G)叫做右线性语言。 * * 文法的乔姆斯基体系 左线性文法(left liner grammar) 设G