オートマトン理論演習問題

オートマトン理論演習問題
2015 年 1 月 20 日
1. アルファベット Σ = {a, b, c} 上の言語，L = {an bm cn+m | n, m ≥ 0} について，以
下の問に答えよ．
(a) L を生成する文脈自由文法（CFG）を示せ．
(b) L を受理するプッシュダウン・オートマトン（PDA）を示せ．
2. 図 1 の推移図で動作が定義される PDA を考える．ただし，スタックの開始記号は Z
で，空スタック受理の PDA である．このとき，図 1 の PDA が受理する言語を生成
する CFG を構成せよ．
図 1: PDA の推移図
3. (a) 次の CFG G1 に対して問いに答えよ．
G1 = ({S, A, B, C}, {a, b, c}, P1 , S)
P1 = {S → Ac, A → aA | BC, B → bA | ε, C → cA | ε}
i. 消去可能な変数を求めて，G1 と等価でかつ ε-規則をもたない CFG G′1 を
求めよ．
ii. G′1 と等価でかつ単位規則をもたない CFG G′′1 を求めよ．
(b) 次の CFG G2 と等価でかつ無用な記号を含まない CFG G′2 を求めよ．
G2 = ({S, A, B, C}, {b, c}, P2 , S)
P2 = {S → AC | bS | b, A → AC, B → bS | b, C → c}
(c) 次の CFG G3 と等価なチョムスキー標準形の CFG G′3 を求めよ．
G3 = ({S, A, B, C}, {a, b, c}, P3 , S)
P3 = { S → ABaC | ABa, A → BC | b | c, B → b, C → c}

Download Report