形式語言與自動(dòng)機(jī)導(dǎo)論

G叫做0型文法(type0grammar)，也叫做短語結(jié)構(gòu)文法(phrasestructuregrammar,enumerable，r.e.)。立，則稱G為1型文法(type1grammar)，或上下文有關(guān)文法(contextsensitiveL(G)叫做1型語言(type1language)或者上下文有關(guān)語言(contextsensitivelanguage,CSL)。α∈V成立，則稱G為2型文法(type2L(G)叫做2型語言(type2language)或者上下文無關(guān)語言(contextfreelanguage,CFL)。3grammar)，也可稱為正則文法(regulargrammar,RG)或者正規(guī)文法。L(G)叫做3型語言(type3language)，也可稱為正則語言或者正規(guī)語言(regularlanguage,RL)。在文法中設(shè)置變量C，充當(dāng)TM中的讀頭的作用，它從左到右掃描0，并且在每次遇到一個(gè)0時(shí)，都用00替換之，這使得當(dāng)它從最左端移到最右端時(shí)，就完成了當(dāng)前串的加倍工作，為了使串中的0再次被加倍，變量D充當(dāng)將這個(gè)“讀頭”從右端移回到最左端的作用。為了標(biāo)記出端點(diǎn)，文法用C向右掃描，將每一個(gè)0變成00，以實(shí)現(xiàn)0DD0D0EE0E向左移動(dòng)，以尋找左端點(diǎn)A

ε對于任一PSGG=(V，T，P，S)，存在TMM，使得L(M)=L(G)。M具有兩條帶，其中一條帶用來存放輸入字符串設(shè)第二條帶上的句型為γ，M按照某種策略在γ中選擇一個(gè)子串α，使α為G的某個(gè)產(chǎn)生式的左部，β，用β替換α。在需要時(shí)，利用適當(dāng)?shù)囊苿?dòng)技術(shù)，讓TM可以實(shí)現(xiàn)將句型中的α替換成β的工與第一條帶上的w進(jìn)行比較，如果相等，就接受；由于G為PSG，所以，在整個(gè)試派生過程中，我們是無法總能根據(jù)當(dāng)前句型的長度來決定該派生是否需要繼續(xù)進(jìn)行下去。這樣一來，對于一個(gè)給定的輸入字符串，如果它不是L(G)的句子，我們構(gòu)造的TM可能會(huì)陷入永不停機(jī)的工作過程中。這從另一方面說明，定理對于任一TMM，存在PSGG=(V，T，P，①設(shè)TMM=(QΓδ,q0BF)，L=(M②讓G可以產(chǎn)生∑*中的任意一個(gè)字符串的變形，然后讓G模擬M處理這個(gè)字符串。如果M接受它，則G就將③變形是讓每個(gè)字符對應(yīng)一個(gè)二元組。[a1,a1][a2,a2]…[anan*，被看成a1a2…anG=((∑∪{ε})×Γ∪{A1,A2,A3}∪Q,∑,P, A2[a,a1][a2,a2]…[an,an]的串； A2在預(yù)生成雙副本子串[a1a1][a2 A3[ε,B]的子串[ε,B][ε,B]……[ε,B]。在派生過 a∈∑∪{ε}，qp∈Q，X,Y∈Γ，如果δ(q,X)=(p,Y,R)，則q[a,X][a, 對于a,b∈∑∪{ε}，qp∈Q，X,Y,Z∈Γ，如果δ(q,X)=(p,Y,L)，則[b,Z]q[a,X]p[b,Z][a, [a,X]qqaqG先將句型中的[、]、Xq[a,X] M=(Q,∑,Γ,δ,q0,￠,$,L(M)={w|w∈(∑-{￠$})*&q∈F使得q0￠w$├*￠αqβ$。 G=(V，T，P，S)，使②用一個(gè)兩道TM模擬G。一道存放字符串LBA均會(huì)停機(jī)，這表明CSL對于任意L，εL，存在LBAM，證明：主要是根據(jù)給定的LBAM構(gòu)造出CSGG。這里的雙副本串是形如[a1,q0￠a1][a2,行為[a,q0￠a$]。（1）對于a∈∑-{￠$}，A1[a,q0￠a]A2a2]…[an,an$]的雙副本串(句型)中的[a1,q0￠a1]，并將生成子串[a2,a2]…[an,an$]的任務(wù)A1[a,（2）對于a∈∑-{￠$}，A2[a,a]A2A2首先生成任意的形如[a1q0￠a1][a2a2]…[an,an$]的雙副本串中的子串[a2,a2]…[an-1,an-1]；（3）對于a∈∑-{￠$}，A2[a,a$]A2[a1q0￠a1][a2,a2]…[an,an$]的雙副本中的子串[an,an$]； q,p∈Q，X,Y,Z∈Γ，X≠$，如果δ(q,X)=(p,Y,R)，則[a,qX][b,Z][a,Y][b,p q,[b,Z][a,qX][b,pZ][a,對于a∈∑，q