文脈自由言語

6.3.1 ^{文脈自由文法}

定義6.3 ^文法G=(ΣN,ΣT,P,S)^{が文脈自由文法}(CFG: context free grammar)^{とは、生成規則}P が

A→α, A∈ΣN, α∈(ΣN∪ΣT)^∗

の形の有限集合からなり、文形式uAv^（u,v∈(ΣN∪ΣT)^{∗）において}Aの前後の文脈に無関係に置 き換え規則が適用できて、

uAv⇒

G vαv

と導出できるような文法である。置き換え規則A→α^{において、。}α=ε^のときはε-^{生成という。}

非終端記号Aを左側に持つ複数の置き換え規則A→α1, . . . ,A→αnがあるとき、記号|^をor^の 意味で使って

A→α1 . . .αn

と表すことがある。

例6.6 ^{文脈自由文法}G1=({S},{0,1},P1,S) P1={S→0S1, S→ε}.

G1の導出は次のようになる。

S⇒

G1

0S1⇒

G1

00S11⇒^∗

G1

0ⁿS1ⁿ ⇒

G1

0ⁿ1ⁿ. これより、言語

L={0ⁿ1ⁿn≧0}

はG1によって生成される文脈自由言語である。

例6.7 ^{文脈自由文法}G2=({S,A,B},{0,1},P2,S) P2: S→0B1A,

A→00S1AA, B→11S0BB.

演習6.6 ^文法G2が生成する言語を帰納法によって示しなさい。

文脈自由文法での導出u⇒

G v^とは、G^のP^{内の生成規則}A→αの左辺に登場する非終端記号A が文形式u内のどこかにあれば、その場所によらずに記号列α^{に置き換えて文形式}v^{が得られる。}

ΣT上の言語L⊆Σ^∗_T^{に対して、}Lを生成する文脈自由文法G^{が存在するとき、}L^{を文脈自由言}

語(CFL: context free language)という。言語階層に関する結果から、文脈依存言語はその真の部

分集合として文脈自由言語を含む。したがって、文脈自由言語は文脈依存文法によって生成される が、その逆、文脈自由文法によって生成できない言語集合が存在する。

定義6.4 ^{文脈自由文法}G =(ΣN,ΣT,P,S)^{に対する導出木}(derivation tree)^（解析木(parse tree)

(1) ^各a∈ΣN∪ΣT に対して、記号a^{をラベルに持つ}1つの頂点だけからなる木（図6.1^）は導 出木である。

a

図6.1 1^頂点a∈ΣN∪ΣTだけからなる導出木

(2) ε-^生成規則A→ε(A∈ΣN)^{に対して木（図}6.2^{）は導出木である。}

A

ε

図6.2 ε-^生成規則A→ε^の導出木

(3) ^{木の根のラベルが}A1, . . . ,An ∈ΣN∪ΣTである導出木をT1, . . . ,Tnとする。G^{の生成規則}

P:A→A1. . .Anに対して、A^{を根とする図}6.3のような木は導出木である。

A

A1 . . . An

T1 T_n

図6.3 ^生成規則A→A1. . .Anからの導出木

(4) ^手順(1),(2),(3)を使って定義される有限木だけが導出木である。

演習6.7 ^例6.7で与えられた文脈自由文法G2の導出木を書いてみなさい。

文法G^の導出A ⇒^∗

G α,(A ∈ ΣN, α∈ (ΣN∪ΣT)^∗)において、各導出で適用された生成規則（被 置き換え記号は1^度に1つだけ）を定めることによって導出木T^{は一意に定まり、}T^{の葉を左か} ら右へ走査した記号列がα^{となっている。導出}A⇒^∗

G αが、その各段階において記号列の最左に ある非終端記号が置き換えられて得られているとき最左導出(leftmost derivation)^{、その各段階} において記号列の最右にある非終端記号が置き換えられて得られているとき最右導出(rightmost derivation)^という。

次の補題から、文脈自由文法の導出は最左導出だけを考えるだけで十分である。

補題6.1 ^導出x⇒^∗

G y^{を文脈自由文法}G=(ΣN,ΣT,P,S)の導出とする。このとき、x^から y^への最 左導出がある。

証明

■

定義6.5 ^{文脈自由文法}G=(ΣN,ΣT,P,S)^がある語w∈L(G)^に対して2つ以上の異なる導出木を 持つとき、G^は曖昧(ambiguous)^という。

例6.8 加法と乗法からなる式を生成する文脈自由文法G3 ={{S,T},{a,b,+,∗},P3,S}

P₃: S→S+SS∗ST, T→x|y.

G3は中置き式(infix)の加乗法の式を生成する。x∗y+x^{の導出は、}(x∗y)+x^またはx∗(y+x) と2つの導出木を持ち、曖昧である。

演習6.8 ^例6.8^{の文脈自由文法}G3で生成される文の導出木が2つ以上ある別の文例を挙げなさい。

演習6.9 ^{次の文脈自由文法}Ga = ({S,A,B},{a,b},P,S)ga曖昧（ある導出の導出過程を表す導出木 が複数ある）であることを示しなさい。

Pa: A→ACCB, A→aAbab, B→bBba, C→aca.

[^ヒント]^導出aabbaの導出過程を複数上げることができる。

文脈自由言語L は、それを生成するどんな文脈自由文法G も曖昧であるとき本質的に曖昧 (inherently ambiguous)という。本質的に曖昧な文脈自由言語が存在する[1]^。

6.3.2 ^{文脈自由文法の例}

生成する言語が非自明な文脈自由文法G=(ΣN,ΣT,P,S)^{を考えてみよう。}

演習6.10 ^{文脈自由文法}G4=({S,A,B,C},{a},P4,S) P4: S→BABBA

A→00S1AA, B→11S0BB

演習6.11 ΣT ={a,b}^{上の任意の回文}(palindrome) {w|w=w^R,w^Rはw^の反転}

を生成する文脈自由文法G7を構成しなさい。

演習6.12 ΣT ={a,b}^{として、言語} {ww^R|w∈Σ^∗_T,w^Rはw^の反転}

を生成する文脈自由文法G6を構成しなさい(^節7.2^の例7.4^{節参照）。}

演習6.13 ΣT ={a,b,c}^{として、言語}

{wcw^R∈Σ^∗_T|w∈ {a,b}^∗,w^Rはw^の反転}

を生成する文脈自由文法G5を構成しなさい。

演習6.14 ^{次の文脈自由文法}G₈=({S,T},{a,b},P₈,S)^{が定める言語}L(G₈)^{を決定しなさい。}

P8: S→aSbT, T→bTaε [^ヒント]

L(G8)={

aⁿb^ma^mbⁿn≧0,m≧0} .

演習6.15 ^{次の文脈自由文法}GN =({S,A,B},{a,b},PN,S)^{が定める言語}L(GN)^{を決定しなさい。}

PN : S→aBbAε A→aSbAA B→bSaBB.

[^ヒント]GNはa^とbの出現回数が等しい言語を生成する。

L(G_N)={

w∈ {a,b}^∗|N_a(w)=N_b(w)}

演習6.16 ^{次の文脈自由文法}Gabc=({S,S1,S2,A,C},{a,b,c},Pabc,S)^{が定める言語}L(Gabc)^を決定し なさい。

Pabc: S→S1CAS2, S1→aS1bε, S2→bS2cε, A→aAε, C→cC.

[^ヒント]Gabcは次の言語を生成する。

L(Gabc)={

aⁱb^jc^k|i= j^または j=k,i,j,k≧0}

演習6.17 ^{次の文脈自由文法}Gab =({S,B},{a,b},Pab,S)^{が定める言語}L(Gab)^{を決定しなさい。}

P9: S→aSbBε, B→bε.

[^ヒント]

L(Gab)={

aⁱb^j0≦i≦ j≦2i} .

演習6.18 ^{文脈自由文法}G9=({S,T,U,X},{a,b,c},P9,S) P9: S→XSX|T,

T→cUc,

U→XUX|a|b|ε, X→a|b.

が定める言語L(G9)^{を決定しなさい。}

[^ヒント]

L(G₉)={

xcycz|x|=|z|,x,y,z∈ {a,b}²} .