オートマトン・形式言語 演習問題 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 ページ参照).
© Copyright 2024 ExpyDoc