オートマトン理論演習問題
2015 年 1 月 13 日
1. 次の生成規則 P をもつ CFG G = ({S}, {a, b}, P, S) はあいまいである．
P = { S → aS | aSbS | ε }
このとき，以下の問に答えよ．
(a) G は，列 aab に対して構文木を二つ持つ．それらを示せ．
(b) G は，列 aab に対して最左導出を二つ持つ．それらを示せ．
(c) G は，列 aab に対して最右導出を二つ持つ．それらを示せ．
2. 次の推移関数 δ をもつ PDA P = ({q0 , q1 }, {a, b}, {A, Z}, δ, q0 , Z) を考える．
δ(q0 , a, Z)
δ(q0 , a, A)
δ(q0 , b, A)
δ(q1 , b, A)
δ(q1 , ε, Z)
=
=
=
=
=
{(q0 , AZ)}
{(q0 , AA)}
{(q1 , ε)}
{(q1 , ε)}
{(q1 , ε)}
次の各語を入力として与えたときの，P の動作を時点表示によって表せ．
(a) ab
(b) aab
(c) aabba
(d) aaabbb
3. 次の言語を受理する PDA を答えよ．最終状態受理にするか空スタック受理にする
かについてはどちらでもよいが，どちらによる受理としたかは解答に明記すること．
(a) {0n 12n | n ≥ 0}．
(b) 0 と 1 の列で，先頭からどの位置までを見ても，1 の個数が 0 の個数を超えな
いものの集合．
(c) 同じ個数の 0 と 1 を含む列の集合．
© Copyright 2024 ExpyDoc
