オートマトン・形式言語 演習問題
2016 年 1 月 26 日
1. アルファベット Σ = {a, b, c} 上の言語，L = {an bm cn+m | n, m ≥ 0} について，以
下の問に答えよ．
(a) L を生成する文脈自由文法（CFG）を示せ．
(b) L を受理するプッシュダウン・オートマトン（PDA）を示せ．
2. Σ = {0, 1} とする．次の言語を認識する有限オートマトンおよびその言語を表現す
る正規表現の両方を答えよ．オートマトンは，DFA, NFA, ϵ-NFA のいずれでもよい．
(a) L1 = {x ∈ Σ∗ | x においてその末尾の記号はそれよりも前に現れない }
(b) L2 = {x ∈ Σ∗ | x 中のどの 0 についてもその直後に 2 回以上の 1 が続く }
(c) L3 = {x ∈ Σ∗ | x の少なくとも末尾の 3 文字のうちの 1 つは 1 である }
(d) L4 = {x ∈ Σ∗ | x は 3 個以上の 0 を含まない }
3. アルファベット Σ = {0, 1} からアルファベット Γ = {a, b} への準同型写像 h を
h(0) = ab, h(1) = bb とする．言語 L5 = L((a + b)∗ (aa + bb)) に対する h−1 (L5 )
を表す正規表現を求めよ．
4. L6 = {wwR | w ∈ {0, 1}∗ } が正規言語でないことを反復補題を用いて証明せよ．
© Copyright 2024 ExpyDoc
