第 3 章 「文脈自由言語」

第 3 章

「文脈自由言語」

3.1

3.2

3.3

3.4

3.5

形式言語と自然言語

Noam Chomsky

1950

N. Chomsky

構文論 syntax

意味論 semantics

語用論 pragmatics 音韻論

phonology 形態論

morphology

言語学

文の構造を研究

語の構造を研究 文の意味を研究

文脈における文の意味を研究 言葉の発音を研究

She loves Neo S

NP VP V NP

PN P

She loves Neo

3.1 文脈自由文法

定義

 文脈自由文法とは４つ組

G = (N, Σ, P, S)

によって定義される。



N:

N

Σ:

Σ

S: S N

P: P

N×(N Σ)*

 P の要素 (A, α) は生成規則とよばれ、 A α → と書かれる。

 α=ε のとき ε 生成規則という。

 非終端記号 A を生成規則の左側にもつ P の要素を A α→ 1, …, A α→ n とするとき、これらをまとめて A α→ 1| …|αn と書くこともある。

　文脈自由文法の例

 例 3.1 ( 例 3.3)

 G=(N, Σ, P, S)



N = {S}



Σ= {a, b}



P = {S ab, S aSb}

 例 3.2 ( 例 3.4)

 G=(N, Σ, P, S)



N = {S, A, B}



Σ= {x, 0, 1}



P = {S xA, A 0|1B, B ε|0B|1B}

　語の導出

導出の定義

 V = N Σ

記号列

u,v V*

u⇒

v

(1) u = xAy, v = xαy (x, y,α V*, A N)

(2) A α

G





n

 V*

w

, …, w

w

⇒

w

⇒

w

w

w

n

*

G は省略することもある

　 G が生成する語、言語

 開始記号 S より w Σ* ∈ が G の生成規則に よって導出されるとき、 w は G の生成する語 とよばれる。また G の生成する言語を

L(G) = { w Σ* | S ∈ ⇒

w}

と書く。

 言語 L Σ* ⊆ に対して L = L(G) となるとき、

G は L を生成するという。

 Σ 上の言語 L S* ⊆ に対して、

L を生成する文脈自由文法が存在するとき、

L は文脈自由言語とよばれる。

　文脈自由言語と CFL

CFL の定義



CFL

すなわち、

CFL =

{ L | L = L(G)

G

}

集合の集合（族）

　導出の例

 例 3.5

 N = {S,A,B}, Σ= {x, 0, 1, +, ・ , ), ( }

 P = {S (S +S) | S → ・ S | xA,

A ε| 1B, B ε|0B|1B|0|1 } → →

 例 3.6

 N = {S}, Σ= { ), ( }

 P = {S SS, S (S), S ()} → → →

 例 3.7

 N = {S}, Σ= {0,1,φ,+, ・ ,*,),( }

 P = {S φ|0|1|(S+S)|(S → ・ S)|S* }

　構文木

定義



ここで、

V = N S ∪

(1)

A V ∈

A

(2)

A→ε

A

A ε

導出の過程を Visualize する道具

定義つづき

(3) T

, …, T

を根のラベルが A

, …, A

∈ で V ある構文木とする。

G の生成規則 A A →

…A

に対して、

A を根とする木

(4) 上記 (1) ～ (3) の規則を使って定義される 有限の木のみを構文木という。

　構文木（２）

A

A

^・・・ A

T

T

　構文木の例

 例 3.8 ( 例 3.1 の導出木 )

S S S S S S

a a a a a a b b b b b b

L(G)

　最左導出

 最左導出と左側順走査





A

u

 例 3.9 ( 例 3.6 の最左導出 )



(())(()())

*

　補題 3.1

補題 3.1

 G=(N,S,P,S) を文脈自由文法とする。

導出 u v ⇒ があるならば、

u から v への最左導出がある。

証明

 u = w

A

w

… w

A

w

(A

∈ N, w

∈ Σ*) とする。

v = w

A

w

A

w

… w

A

w

A

⇒ v

(1 i k) ≦ ≦ v = w

v

w

v

w

… w

v

w

*

左側順走査による 最左導出とする

① ②

3.2 プッシュダウンオートマト ン  概念図と基本動作

プッシュダウンストア

a

a

a

q q

有限制御部

入力テープ

A B Z

A B A

push

A

pop

(1)

(2)

(3)

　プッシュダウンオートマトンの 定義 定義

 プッシュダウンオートマトン (pda) は７つ組 M=(K, Σ,Γ,δ, q

, Z

, F)

によって定義される。



K :



Σ:



Γ:



q

:

q

K



F :

F K



Z

:

Z

Γ



δ :

K×(S {e})×G×K×G*

(q,a,Z,p,α) δ

(p,α) δ(q,a,Z)

非決定的な定義 であることに注

意

非決定的な定義 であることに注

意

　 PDA による語の受理

 計算状況

 状態

q K

w S*

a Γ*

(q,

w,α)



α=Zβ

Z

 K×Σ*×Γ* 上の関係├



(q,ax,Zα)├

(p,x,βα) (p,β) δ(q,a,Z)



(q,ax,Zα)

(p,x,βα)



a =ε

ε

 関係├ M の反射的推移閉包を├ M とかく

 PDA による語の受理

 最終状態によって受理　→　

L(M)

 最終状態かつ空ストアによって受理　→　

N(M)

*

　命題 3.2

命題 3.2

 言語

L Σ*

(1) ある

pda M

L=L(M)

(2) ある

pda M

L=N(M)

証明

 (1)→(2)



M

w

(q

, w, Z

) ├

(f,ε,γ)

となり、さらに

ε

γ

M’

 (2)→(1)

 上と似たやり方で、今度は逆に

M’

M

*

　決定性 PDA と非決定性 PDA

 決定性と非決定性

 非決定性プッシュダウンオートマトン

 計算状況に対して一意に次の計算状況が決まらない。

 決定性プッシュダウンオートマトン

 任意の計算状況に対して次の計算状況が一意に決まる。

決定性 PDA の定義



PDA M=(K,Σ,Γ,δ,q

,Z

,F) は、次の (1)(2)

(1) |δ(q, a, Z)| 1

(a Σ {ε})

(2) δ(q,ε,Z) ≠φ

a Σ

δ(q,a,Z)=φ

(2) が無いと、入力語を消費する前に ε 動作をするため、非決定的な動作になる。

　決定性 PDA と非決定性 PDA の 違い

 非決定性 PDA の場合は命題 3.2 が成り立つ

 決定性 PDA の場合は成り立たない

 決定性

PDA

ε

(q

,ε,Z

)├

(q,ε,ε) (q F)

となる。するとどんな入力に対しても

(q

, x, Z

)├

(q, x,ε)

となり、入力

x

したがって、

ε N(M) N(M)={ε}

*

*

　クラス NPDA と DPDA

定義

 (1) NPDA={L |

npda M

L=L(M)}

 (2) DPDA={L |

dpda M

L=L(M)}

命題 3.3

 L

,L

NPDA

L

L

NPDA

証明



定理 3.4

 CFL = NPDA

 文脈自由言語のクラスと非決定性プッシュダウン オートマトンによって受理される言語のクラスは 一致する。

 2 つの補題に分けてこの定理を証明する。

 補題

3.5 CFL⊆NPDA

 補題

3.6 NPDA⊆CFL

3.3 文脈自由文法と PDA

　補題 3.5 CFL ⊆ NPDA

 この補題の意味

 任意の言語 L  _{CFL について、}

L  NPDA

L

npda

 証明のアイデア

 L CFL ∈ とし、 L Σ* ⊆ を生成する文脈自由文 法を G = (N,Σ, P, S) とする

 この G に対応する npda M をつくり、

L(G) = N(M) となることを示せばよい

NPDA

CFL

　補題 3.5 の証明 (1)

 言語

L

npda M = (K, Σ,Γ,δ, q

, Z

, F)



K = {q

}



Γ= N Σ



q



S N

Z



F = {q

}

 遷移関係



(i)δ(q

,ε, A) = {(q

,α) | A α P}

(ii)δ(q

, a, a) = {(q

,ε)} (

a Σ)

注：これは、文脈自由文法から等価な

PDA

　補題 3.5 の証明 (2)

 L(G) = N(M) を証明するぞ！

 まずは

X N, u Σ*,



N(N Σ)* {ε}

次の

(a) (b)

(a)

X uα

(b) (q

, u, X) (q

,ε,α)



(a) (b)

 長さが

0

u =ε, α= X

 最左導出の長さが

n

このとき長さ

n+1

X u

をとる。ただし

u Σ*,α (N Σ)* {ε}

入力から u を消費してストアの X を α に変える

*

*

n+1

この最左導出は、

X v

Aβ vγβ

(

v Σ*, A γ P)

のように、長さ

n

1

u = vx, x Σ*,γβ= xα

(q

, v, X) (q

,ε, Aβ)

(q

, vx, X) (q

, x, A)

(q

, x, x  )

(i)

= x 

├

(q

, , )

(ii)

このようにして

(q

, u, X) (q

,  ,  )

よって

(a) (b)

　補題 3.5

の証明 (3)

X

A

v β

(xθ) γ

*

*

*

　補題 3.5 の証明 (4)



(b) (a)

 計算のステップ数についての帰納法で証明する。

 ステップ数が 0 の場合は自明。

 ステップ数が n 以下のとき成立すると仮定する。長さ n+1 の計 算 (q0, u0, a0) ├ ・・・├ (q0, un,an) (q├ 0, un+1,an+1)

をとる。ただし u0 = u, un+1 =ε, a0 = X, an +1 = a とする。

 n+1 番目のステップで (i) の遷移（ ε 動作）が使われている場合：

上の計算は

(q0, u, X)├ⁿ (q0,ε, Aβ) (q├ 0,ε,γβ)

と分解できる。ただし A γ P,γβ=α→ ∈ である。

帰納法の仮定により、最左導出 X uAβ⇒

が存在する。 A γ P → ∈ であり、また u Σ*∈ だから、

X uAβ uγβ⇒ ⇒ は最左導出である。

よって X uα⇒ なる最左導出が存在する。

*

*

*

　補題 3.5 の証明 (5)

 n+1 番目のステップで (ii) の遷移が使われている場合：

X

(ii)

m(2 m n+1)

m

1

(i)

t(m t n+1)

t

(ii)

 すると、計算

(q

, u, X)├

(q

,ε,α)

(q

, vx, X)├

(q

, x, Aβ )

(q

, x,γβ)

├ ^n-m+2

(q

,ε,α)

と分解できる。また

(q

, vx, X)├

(q

, x, Aβ)

(q

, v, X)├

(q

,ε, Aβ)

X vAβ

が存在する。すると

X vAβ vγβ

*

* （ m-1 回目の遷移に対応）

　補題 3.5 の証明 (6)

 以上により

(a)

(b)

(a)

X u



(b) (q

, u, X) (q

,  ,  )

 補題

3.1

G

w Σ*

S w (q

, w, S) (q

,  ,  )

となる。したがって

L(G) = N(M)

命題

3.2

L NPDA

補題

3.1

G = (N,  , P, S)

u v ⇒

u

v

補題

3.1

G = (N,  , P, S)

u v ⇒

u

v

*

* *

*

*

　例 3.13

 文脈自由文法 G = (N, Σ, P, S) を



N = {S}



Σ= {a, b}



P = {S aSb, S ab}

とする。このとき補題 3.5 で構成される npda の 遷移関数 δ は次のようになる

q x Z ^{δ(q, x, Z)}

q

 S {(q

, aSb), (q

, ab)}

q

a a {(q

,  )}

q b b {(q ,  )}

現在の状態 入力ヘッダが見ている記号 ストアのヘッダが見ている記号

　補題 3.6 NPDA CFL ⊆

 この補題の意味



L  NPDA

L  _CFL

L

CFL

 証明のアイデア

 L NPDA

L

受理する

npda

M=(K,Σ,Γ,δ, q

, Z

, F)



M

G

N(M) = L(G)

CFL

NPDA

　補題 3.6 の証明 (1)

 L を生成する文脈自由文法 G=(N,Σ, P, S) を（天下り的に）定義

 N = (K×Γ×K) {S}

 P

(i)

p F

S (q

, Z

, p)

(ii) (p, Z

Z

) δ(q, a, Z) (k

1, a S {ε})

q

, q

, …,q

K

(q, Z, q

) a(p, Z

, q

)(q

, Z

, q

)

(q

, Z

, q

)

(iii) (p,ε) δ(q, a, Z) (a S {ε})

(q, Z, p) a

　補題 3.6 の証明 (2)

 L(G) = N(M)

 その前に、次の

(a) (b)

(a) (q, Z, p) x

(b) (q, x, Z) (p,ε,ε)



(a) (b)

 長さが 1 のときは、生成規則 (iii) により x S {ε} ∈ ∪ で (p,ε) d (q, x, Z )∈

となっている。したがって (q, x, Z) (p,ε,ε) ├ となる。

長さ n 以下の導出に対して成立することを仮定する。

 長さ n+1 2 ≧ の導出 (q, Z, p) x⇒

をとる。導出の長さが 2 以上だから一番初めに適用される 生成規則は (ii) の形のものである。

*

*

　補題 3.6 の証明 (3)

　 このとき上の導出は

(q, Z, p) a(q

, Z

, q

)(q

, Z

, q

)

(q

, Z

, p)

x

(q

, Z

Z

) d (q, a, Z)

すると、

x = ax

x

(x

Σ*)

i (1 i k)

n

(q

, Z

, q

) x

となる。 ただし

q

= p

帰納法の仮定より

(q

, x

, Z

) (q

,ε,ε) (1 i k)

(q

, x

, Z

) (q

, x

x

, Z

Z

) (q

, x

x

, Z

Z

)

├ 　･･･

(q

, x

, Z

) (p,ε,ε)

*

*

*

*

*

　補題 3.6 の証明 (4)



(b) (a)

法）



(iii)

(q, Z, p) x

P

よってステップ数が

1

n+1 2

(q, x, Z)├

(p,ε,ε)

とする。これを最初の

1

n

n 1

1

Z

ε

(q, x, Z) (r, y, Z

Z

) ├

(p,ε,ε)

となる。ここで

x = ay, a Σ {ε}

(r, Z

Z ) δ(q, a, Z)

　補題 3.6 の証明 (5)

 各 Zi はいずれポップされるので、

分解 y = y1･･･ yk (yi∈Σ*, 1 i k) ≦ ≦ と状態 q1･･･ qk が存在して

、

各 i (1 i k) ≦ ≦ に対して、 n 以下のステップ数で (qi, yi, Zi ) (q├ i+1,ε,ε)

となる。ただし q1 = r , qk+1 = p とする。

帰納法の仮定より

(qi, Zi, qi+1) y⇒ i (1 i k)≦ ≦ となる。 (ii) より

(q, Z, p) a(q⇒ 1, Z1, q2) ･･･ (qk, Zk, p ) だから

(q, Z, p) a(q⇒ 1, Z1, q2 ) ･･･ (qk, Zk, p ) ay⇒ 1･･･ yk

となる。 よって (q, Z, p) x ⇒ となる。

*

*

*

*

　補題 3.6 の証明 (6)

 以上により

(a)

(b)

(a) (q, Z, p) x

(b) (q, x, Z) (p,ε,ε)

 そこで

x Σ*

S x

(i)

ある状態

p F

S (q

, Z

, p) x

したがって

(q

, x, Z

) (p,ε,ε)

となり、

x

M

逆に

x

M

S x

*

*

*

*

*

*



M = (K,Σ,Γ,δ, q

, Z

, F)

{a

b

| n

1}

3.12

npda

3.6

G=(N, S, P, S)

N = {q

, q

}×{A, Z

}×{q

, q

} {S}

P

S (q

, Z

, q

)

(q

, Z

, q

) a(q

, A, q

) (q

, Z

, q

) a(q

, A, q

)

(q

, A, q

) a(q

, A, q

) (q

, A, q

) (q

, A, q

) a(q

, A, q

) (q

, A, q

) (q

, A, q

) a(q

, A, q

) (q

, A, q

) (q

, A, q

) a(q

, A, q

) (q

, A, q

) (q

, A, q

) b

　例 3.14

無駄な生成規則 が多いよ ( ・∀・ )

 以下の補題が証明された

 補題 3.5 CFL⊆NPDA

 補題 3.6 NPDA⊆CFL

 すなわち

 文脈自由言語のクラスと非決定性プッシュダウ ンオートマトンによって受理される言語のクラ スは 一致する。（言語を定義する能力が等しい）

　 3.3 節の結論

定理 3.4

CFL = NPDA 定理 3.4

CFL = NPDA

3.4 正規文法と有限オートマト ン

A  wB (A, B  N, w  Σ* ) A  w

A  wB (A, B  N, w  Σ* ) A  w

右線形文法

A  Bw (A, B  N, w  Σ* ) A  w

A  Bw (A, B  N, w  Σ* ) A  w

左線形文法 正規文法

　例 3.15 右線形文法の例

N = {S, A}

P = {S  1A, A  0A, A   } S

A

1 0

A

0

A

0 

A

　例 3.16 左線形文法の例

N = {S}

P = {S  S0, S  1}

S S

1 0

S

0 S

0 S

0

　定理 3.7

定理

3.7

 言語

L Σ* ⊆

(1)

(3)

。

(1) L

(2) L

(3) L

正規文法正規文法

有限オートマトン 有限オートマトン 正規表現正規表現

　証明 (1) (2) ⇒

N = {S, A}

P = {S  1A, A  0A, A   } 例 3.15 の場合

S 1 A  f

0

M :

L(M) = L(G) を帰納法を用いて証明する。

　証明 (2) (3) ⇒

M : _q

0

1 q

0 0

1

G = (K,Σ, P, q

)

P = { q

 1q

, q

 0q

, q

 1q

, q

 0q

, q

  }

L(M) = L(G) を帰納法を用いて証明する。

例：　

1

　証明 (1) (3); (3) (1) ⇒ ⇒

N = {S, A}

P = {S  1A, A  0A, A   }

S

A

1 0

A

0

A

0 

A

N = {S, A}∪{S  } P = {S  

A  S1, A  A0, S   A  }

A

1 0

A

0 A

 S



S 

A

0

3.5 文脈自由文法の性質

 この節の内容

 定理 3.8 　　 ε 生成規則消去定理

 定理 3.9 　　鎖生成規則の消去定理

 定理 3.10 　 Chomsky 標準形への変形

 定理 3.11 　挿入定理

　定理 3.8 ε 生成規則消去定理

定理 3.8

 文脈自由文法 G = (N,Σ , P, S ) に対して、

次の (1) － (3) を満たす文脈自由文法 G ’ = ( N ’ ,Σ , P’, S’ )

(1) 　

L(G  ) = L(G )

(2) ε

∈ ^{L(G )}

^G’

^ε

ち、

　　それは

S’ ^ ε

(3) G’ の開始記号

S ’

P ’



G

G’

定義する。

 その前準備として、元の

G

N

ε

N

 こうして作った

G’

(2)

(3)

 残る (1) L(G’ ) = L(G ) を証明する。



L(G’ ) L(G )



L(G’ ) L(G )

　証明の手引き

N N

ε

　証明 (1)

証明

 N ^ = N {S ∪ ^ }

 P ^

(i)   _{L(G )}

S ^{ }

(ii) S ^ S

(iii) A  

A





A



 _P,

A

 _{N Σ} ∪ (1  i  k), ^

 _N

_*

ならば、 A  A

A

この

P’

ε

　証明 (2)

 L(G  ) L(G) ⊆



(i)

L(G )   L(G  )

ここで、

S 

w (w  Σ

)

S 

S 

w

 L(G  ) L(G)



(b) A  N Σ

A 

w, w Σ

A 

w



(b)



(b)

S 

w, w Σ

S 

w

S  

w

*

* *

　例 3.17

 G = (N,Σ , P, S ) を次の生成規則をもつ 文脈自由文法とする。

S ^ AB

A ^ ABAC | B | a B ^ C | b | 

C ^ B | c | 

ε

G’

　定理 3.9 鎖生成規則の消去定 理

定理 3.9

 文脈自由文法 G = (N,Σ , P, S ) に対して、

次の (1)-(3) を満たす文脈自由文法 G ^ = ( N,Σ , P ^ , S )

(1)  ∈ L(G )

S  

(2) A   ( |  |  2, ∈ ((N Σ ∪  {S})*) (3) A  a ( a 

)

(4) L(G  ) = L(G )

注：

S

　証明の手引き



G

G’

 その前準備として、もとの

G

N

、鎖生成規則であるような集合

N

(A)

 こうして作った

G’

 残る (4) L(G’ ) = L(G ) を証明する。



L(G’ ) L(G )



L(G’ ) L(G )

N _N

_(A)

鎖生成規則

　証明 (1)

証明

 N, S は同じ

 P  は次のとおり、

P  = {A  |



B N ∈

(A) [B  ∈P かつ  N] }

 N

(A) = {B  N | A  ^*

B } ( n = |N | )

　証明 (2)

 L(G  ) L(G) ⊆

 A   P 

B  N

(A)

A 

B 



A 





A 

w

A 

w

L(G  ) L(G )

 L(G  ) L(G ) ⊇

 A  N, w  Σ

A 

w

A 

w





S 

w, w  Σ

S 

w

L(G’) L(G)

* * *

* *

t *

*

t

　例 3.18

 G = (N,Σ, P, S ) を次の生成規則をもつ 文脈自由文法とする。

S  A

A  AB | a B  C | b C  A | c

鎖生成規則をなくした

G’

　 Chomsky 標準形

定義

 G = (N,Σ, P, S ) はその生成規則の形が A  BC (A, B, C N ) ∈

または，

A  a (A N, a ∈ ∈Σ )

のとき Chomsky 標準形であるという。

 注： Chomsky 標準形は空語  を含まない。

　定理 3.10 Chomsky 標準形への変形

定理 3.10



G = (N,Σ, P, S )

L(G )  {  }

Chomsky

文脈自由文法

G  = (N  ,Σ, P  , S  )

　証明

証明

 定理

3.9

G

S  

A   ( |  |  2,   ((N Σ ∪  {S})*)

A  a ( a 

)

このとき

G

A  X

X

X

X

X

X

(X

 (N  )  {S}, k  2)

Y

Z

Z

 Y

Z

Z

 Y

Z

・

・

・

Y

 a

X

 a

　例 3.19

 G = (N,Σ, P, S ) を次の生成規則をもつ 文脈自由文法とする。

S  AaAA A  a

等価な

Chomsky

G’

　定理 3.11 挿入定理

定理 3.11

 G = (N,  , P, S )

このとき整数

p(G)

|z| > p(G)

z  L(G)

z

z = u v w x y

で次の (1)



(1) すべての

q  0

u v

w x

y  L(G)

(2) v

 

x  

(3) |v w x|

 p(G)

　証明の手引き

 ( 天下り的に ) 適当な p(G) をとる。

 |z| > p(G) を満たす z L(G) ∈ について、

z の導出に対応する構文木を解析する。

 以上の p(G) 、 z について、 (1)(2)(3) が

それぞれ成り立つことを確かめる。

　証明（ p(G) ）

r

m

 構文木の枝分かれの最大数は、

r = max{ |  | | A   P }

 m  1 に対して、高さ m の構文木は

高々 r

個の葉しかもたないことに注意。

 p(G) = r

とおく。

　証明（ w を導出する構文木）

 p(G) = r

 z  L(G) は |z| > p(G) を満たしているとする。

 S  z を， z を生成する最短の導出と仮定し、

この導出に対応する構文木を T とする。

S

z ( |z| > r

) 2|N|+1

以上

*

　証明（根から葉への最長パス

 ）

S

z ( |z| > r

) 2|N|+1

以上

X

X

X

a

・・・

・

・

・

パス

 : S, X

, X

,

, X

, a

X

T

T

( 0  i  t + 1 ) T

h

X

X

　証明（抽き出し法）

h

 h

 ・・・  h

= 1

h

> r

 1 だから、ある s が存在して h

> r

 h

となる。

・・・

・・・

・

・

・

・

・

・

・・・ ・・・

T

T

h h

2|N|+1

X

= X

= X

= A (s  i < j < k  t)

X

= X

= X

= A

(s  i < j < k  t)

　証明（ (3) |v w x|  p(G) ）

X

= X

= X

= A (s  i < j < k  t)

X

= X

= X

= A (s  i < j < k  t)

・・・

・・・

・

・

・

X

X

S

u v w x y

s  i < j

S  u X

y X

 v X

x X

 w

S  u X

y X

 v X

x X

 w

*

*

*

　証明（ ⁽²⁾ v   または x   ）

・・・

・・・

・

・

・

X

=A X

=A S

u v w x y

v = x = 

A = X

= X

X

 X

z

S  z

。

*

*

S  u X

y X

 v X

x X

 w

S  u X

y X

 v X

x X

 w

*

*

*

　証明（ ⁽¹⁾

q  0 に対して， u v

w x

y  L(G) ）

・・・

・・・

・

・

・

X

=A X

=A S

u v w x y



q  0

S  uAy  uvAxy 

 uv

Ax

y  uv

wx

y u v w x y L(G)

S  u A y A  v A x A  w

S  u A y A  v A x A  w

*

*

*

* * * * *

　例 3.20

 L = {a

b

c

| n  0} が文脈自由言語でない

ことを挿入定理を用いて証明せよ。

3.6 決定性プッシュダウンオート マトン

 DPDA は和集合の演算について閉じていない

。

 L

= {a

b

| n 1}

L

= {a

b

| n 1}

 L

L

NPDA

 L

L

 DPDA ( 定理 3.13)

 よって DPDA≠NPDA 。（系 3.13 ）

 証明（略）