形式语言复习资料

形式语言与自动机理论（电子版笔记）第二章文法2.1文法的形式定义文法(grammar)G=(V，T，P，S)V——为变量(variable)的非空有穷集。A∈V，A叫做一个语法变量(syntacticVariable)，简称为变量，也可叫做非终极符号。它表示一个语法范畴。所以，本文中有时候又称之为语法范畴。T——为终极符(terminal)的非空有穷集。a∈T，a叫做终极符。由于V中变量表示语法范畴，T中的字符是语言的句子中出现的字符，所以，有V∩T=Φ。S——S∈V，为文法G的开始符号(startsymbol)。P——为产生式(production)的非空有穷集合。P中的元素均具有形式α→β，被称为产生式，读作：α定义为β。其中α∈(V∪T)+，且α中至少有V中元素的一个出现。β∈(V∪T)*。α称为产生式α→β的左部，β称为产生式α→β的右部。产生式又叫做定义式或者语法规则。约定⑴对一组有相同左部的产生式α→β1，α→β2，…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(candidate)。⑵使用符号英文字母表较为前面的大写字母，如A，B，C，…表示语法变量；英文字母表较为前面的小写字母，如a，b，c，…表示终极符号；英文字母表较为后面的大写字母，如X，Y，Z，…表示该符号是语法变量或者终极符号；英文字母表较为后面的小写字母，如x，y，z，…表示由终极符号组成的行；希腊字母α，β，γ…表示由语法变量和终极符号组成的行推导(derivation)设G=(V，T，P，S)是一个文法，如果α→β∈P，γ，δ∈(V∪T)*，则称γαδ在G中直接推导出γβδ。γαδγβδ读作：γαδ在文法G中直接推导出γβδ。“直接推导”可以简称为推导(derivation)，也称推导为派生。归约(reduction)γαδγβδ称γβδ在文法G中直接归约成γαδ。在不特别强调归约的直接性时，“直接归约”可以简称为归约。对于G我们有以下推导：SA使用产生式S→ASAB使用产生式S→ABA0使用产生式A→0A0A使用产生式A→0AA00A使用产生式A→0A…A000…0使用产生式A→0语法范畴A代表的集合L(A)={0，00，000，0000，……}={0n|n≥1}；语法范畴B代表的集合L(B)={1，11}语法范畴S代表的集合L(S)=L(A)∪L(A)L(B)={0，00，000，0000，…}∪{0，00，000，0000，…}{1，11}={0，00，000，0000，…}∪{01，001，0001，00001，…}∪{011，0011，00011，000011，…}语言(language)L(G)={w|w∈T*且Sw}句子(sentence)w∈L(G)，w称为G产生的一个句子。句型(sententialform)G=(V，T，P，S)，对于α∈(V∪T)*，如果Sα，则称α是G产生的一个句型。2.2文法的构造例1构造文法G，使L(G)={0，1，00，11}构造：({S}，{0，1}，{S0，S1，S00，S11}，S)({S，A，B}，{0，1}，S→0）例2构造文法G，使L(G)={wwT|w∈{0，1，2，3}+}S→HEH→0|1|2|3|0H|1H|2H|3HE→0|1|2|3|E0|E1|E2|E3难以生成L(G)。根据{wwT|w∈{0，1，2，3}+}的句子的特点（对应位置相等），设w=a1a2…an，从而有wT=an…a2a1，故wwT=a1a2…anan…a2a1，满足f(wwT，i)=f(wwT，|wwT|-i+1)。递归地定义L⑴对a∈{0，1，2，3}，aa∈L；⑵如果x∈L，则对a∈{0，1，2，3}，axa∈L；⑶L中不含不满足(1)、(2)任何其他的串。根据递归定义中的第一条，有如下产生式组：S→00|11|22|33再根据递归定义第二条，又可得到如下产生式组：S→0S0|1S1|2S2|3S3从而，G1：S→00|11|22|33|0S0|1S1|2S2|3S32.3文法的乔姆斯基体系文法G=(V，T，P，S)G叫做0型文法，也叫做短语结构文法(,PSG)。L(G)叫做0型语言。也可以叫做短语结构语言(PSL)。如果对于α→β∈P，均有|β|≥|α|成立，则称G为1型文法，或上下文有关文法(CSG)。L(G)叫做1型语言或者上下文有关语言(CSL)。如果对于α→β∈P，均有|β|≥|α|，并且α∈V成立，则称G为2型文法，或上下文无关文法(CFG)。L(G)叫做2型语言或者上下文无关语言(CFL)。如果对于α→β∈P，α→β均具有形式A→wA→wB其中A，B∈V，w∈T+。则称G为3型文法，也可称为正则文法(RG)或者正规文法。L(G)叫做3型语言，也可称为正则语言或者正规语言(RL)。其中0型∈1型∈2型∈3型⑴如果一个文法G是RG，则它也是CFG、CSG和短语结构文法。反之不一定成立。⑵如果一个文法G是CFG，则它也是CSG和短语结构文法。反之不一定成立。⑶如果一个文法G是CSG，则它也是短语结构文法。反之不一定成立。⑷相应地，各文法定义的语言，上述结论也成立。线性文法(linergrammar)设G=(V，T，P，S)，如果对于α→β∈P，α→β均具有如下形式：A→wA→wBx其中A，B∈V，w，x∈T*，则称G为线性文法。线性语言(linerlanguage)L(G)叫做线性语言右线性文法(rightlinergrammar)设G=(V，T，P，S)，如果对于α→β∈P，α→β均具有如下形式：A→wA→wB其中A，B∈V，w，x∈T*，则称G为右线性文法。右线性语言(rightlinerlanguage)L(G)叫做右线性语言。左线性文法(leftlinergrammar)设G=(V，T，P，S)，如果对于α→β∈P，α→β均具有如下形式：A→wA→wBx其中A，B∈V，w，x∈T*，则称G为左线性文法。左线性语言(leftlinerlanguage)L(G)叫做右线性语言。第三章有穷状态自动机3.1语言识别文法G=(V，T，P，S)，若w∈T*，当sw则存在ws，称w是L（G）的句子，否则不是。其中sw称为规约，ws称为回溯。⑴系统具有有穷个状态，不同的状态代表不同的意义。⑵系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。⑶系统中只有一个开始状态。⑷系统中还有一些状态表示目前为止所读入的字符构成的字符串是语言的一个句子。有穷状态控制器(FSC)的处理机制⑴读入读头正注视的字符an。⑵根据当前状态和读入的字符改变有穷控制器的状态。⑶将读头向右移动一格（指针指向a1n）。3.2有穷状态自动机qq),(ˆ)),,(ˆ(),(ˆawqwaq),()),,(ˆ(),(ˆ),(ˆaqaqaqaq有穷状态自动机(finiteautomaton,FA)M=(Q，∑，δ，q0，F)Q——状态的非空有穷集合。q∈Q，q称为M的一个状态(state)。∑——输入字母表。输入字符串都是∑上的字符串。q0——q0∈Q，是M的开始状态，也可叫做初始状态或者启动状态。δ——状态转移函数，有时候又叫做状态转换函数或者移动函数。F——FQ，是M的终止状态集合。q∈F，q称为M的终止状态，又称为接受状态。现将δ扩充为：Q×∑*→Q对任意的q∈Q，w∈∑*，a∈∑，定义(1)(2)(3)M接受(识别)的语言对于x∈∑*若δ(q，w)∈F，则称x被M接受，若δ(q，w)F，则称M不接受x。L(M)={x|x∈∑*且δ(q，w)∈F}称为由M接受(识别)的语言例：构造一个DFA，它接受的语言为{x000y|x，y∈{0，1}*}即时描述x，y∈∑*，δ(q0，x)=q,xqy称为M的一个即时描述，表示xy是M正在处理的一个字符串，x引导M从q0启动并到达状态q，M当前正注视着y的首字符。├M符为M的所有即时描述集合上的二元关系。α├nMβ：表示M从即时描述α经过n次移动到达即时描述β。α├Mβ：表示M从即时描述α经过至少1次移动到达即时描述β。α├*Mβ：表示M从即时描述α经过若干步移动到达即时描述β。引领的串能引导FA从开始状态到达q的字符串的集合为：set(q)={x|x∈∑*，δ(q0，x)=q}对于任意一个FA，M=(Q，∑，δ，q0，F)我们可以按照如下方式定义等价关系RM：对x，y∈∑*，xRMyq∈Q，使得x∈set(q)和y∈set(q)同时成立。3.3不确定状态机{x|x∈{0，1}*，且x含有子串00或11}的FA如下：不确定的有穷状态自动机(NFA)的形式定义M是一个五元组，M=(Q，∑，δ，q0，F)，其中Q、∑、q0、F的意义同DFA。δ：Q×∑→2Q，对(q，a)∈Q×∑，δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，可以选择地将状态变成p1、或者p2、…、或者pm，并将读头向右移动一个ˆ),(),(ˆaqaqPqwqwP),(ˆ),(ˆPqaqaP),(),()},(),,(ˆ|{)(),(ˆarpwqrpPPCLOSUREwaq)(),(ˆqCLOSUREqPppCLOSUREPCLOSURE)()(QQ22*PqwqwP),(),(带方格而指向输入字符串的下一个字符。进一步扩充δ的定义域：：对任意的PQ，w∈∑*，M接受(识别)的语言x∈∑*，如果δ(q0，w)∩F≠Φ，则称x被M接受，如果δ(q0，w)∩F=Φ，则称M不接受x。L(M)={x|x∈∑*且δ(q0，w)∩F≠Φ}，称为由M接受(识别)的语言。3.4带空移动的有限自动机例：构造接受语言{0n1m2k|n，m，k≥0}的NFA在允许的某状态下，不读入任何字符，而仅让FA的状态发生移动，即ε-NFA带空移动的不确定的有穷状态自动机(ε-NFA)M=(Q，∑，δ，q0，F)，其中Q、∑、q0、F的意义同DFA，δ：Q×(∑∪{ε})→2Q若(q，a)∈Q×∑δ(q，a)={p1，p2，…，pm}表示M在状态q读入字符a，可以选择地将状态变成p1、p2、…或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符。若q∈Qδ(q，ε)={p1，p2，…，pm}表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、…或者pm。也可以叫做M在状态q做一个空移动(又可以称为ε移动)，并且选择地将状态变成p1、p2、…或者pm。进一步扩充δ的定义域：δ：2Q×∑*→2Q。定义：PQ，q∈Q，w∈∑*，a∈∑。（1）-CLOSURE(q)={p|从q到p有一条标记为ε的路}。（2）（3）（4）进一步扩展移动函数：2Q×∑→2Q，对(P，a)∈2Q×∑：（5）（6）在ε-NFA中，对任意a∈∑，q∈Q，，需严格区分。例：对于所示的ε-NFA3.5FA是正则语言的识别器FA与右线性文法对于DFA：M=(Q，∑，δ，q0，F)，基于形式为a1a2…an，有下列推导：⑴M按照句子中字符的出现顺序，从开始状态q0开始，依次处理字符a1a2…an，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状态。⑵它每次处理且仅处理一个字符：第i步处理输入字符ai。⑶对应于使用δ(q，a)=p的状态转移函数的处理，相当于是在状态q完成对a的处理，然后由p接下去实现对后续字符的处理。⑷当δ(q，a)=p∈F，且a是输入串的最后一个字符时，M完成对此输入串的处理。定理：FA接受的语言是正则语言例：与有图DFA等价的正则文法qs→0|0q0|1q1q0→0|0q01q1q1→0q2|1|1q0q2→0q1|1q2FA与左线性文法（1）按照推导来说，句子a