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

オートマトン・形式言語 演習問題
2014 年 12 月 23 日
1. 次の生成規則をもつ文脈自由文法(CFG)G1 = ({S}, {a, b, 0, 1}, P, S) を考える.
P = { S → a | b | Sa | Sb | S0 | S1S }
このとき,次の 3 つの列が L(G1 ) に属するか否かをそれぞれ答えよ.属する場合は
導出過程を1つ示せ.
(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 ページ参照).