オートマトン・形式言語演習問題

オートマトン・形式言語演習問題
2014 年 12 月 23 日
1. 次の生成規則をもつ文脈自由文法（CFG）G1 = ({S}, {a, b, 0, 1}, P, S) を考える．
P = { S → a | b | Sa | Sb | S0 | S1S }
このとき，次の 3 つの列が L(G1 ) に属するか否かをそれぞれ答えよ．属する場合は
導出過程を１つ示せ．
(a) baa
(b) 0a1b
(c) a1b1a0
2. 次の生成規則をもつ CFG G2 = ({S, A, B}, {0, 1}, P, S) を考える．
P = { S → A1B,
A → 0A | ε,
B → 0B | 1B | ε }
このとき，次の 2 つの列について，最左導出と最右導出をそれぞれ求めよ．
(a) 00101
(b) 1001
3. アルファベット Σ = {0, 1} 上の次の言語を生成する文脈自由文法を与えよ．
(a) {0n 1n | n ≥ 1}
(b) {0n 1m | n > m ≥ 0}
(c) {0n 1m | n ̸= m, n, m ≥ 0}
(d) {wwR | w ∈ Σ∗ }
(e) 0 と 1 の出現個数が同じである列の集合
(裏へ続く)
4. CFG は，どの生成規則の本体も高々一つの変数を持ち，しかもその変数が右端にあ
るとき，右線形であるという．よって右線形文法の規則は A → w もしくは A → wB
の形をしている．ここで，A, B は変数 (非終端記号)，w は 0 個以上の終端記号の列
である．このとき，以下の問に答えよ．
(a) 図 1 のオートマトンが認識する正規言語 L を考える．このとき，L を生成する
右線形文法を作成せよ．
ヒント： DFA の各状態を，右線形文法における変数に対応させればよい．
0
q
1
p
0,1
図 1: 決定性有限オートマトン
(b) 以下の生成規則をもつ右線形文法 G = ({S, A, B}, {0, 1}, P, S) を考える．この
文法が生成する言語を認識するオートマトンを作成せよ．
P = { S → 1A | 1,
A → 1B,
B → 0A | 0 }
ヒント：各変数に対応する状態の他に受理状態を用意し，NFA を作成する．
注: CFG が生成する言語は必ずしも正規言語ではない．一方で，右線形文法が生成
する言語はつねに正規言語である．また，どの正規言語についても，ある右線形文
法で生成できる (教科書 204 ページ参照)．

Download Report