演習問題

オートマトン・形式言語 演習問題
2014 年 12 月 2 日
1. アルファベット Σ = {0, 1, 2} からアルファベット T = {a, b} への準同型写像 h を以
下のように定める.
h(0) = a, h(1) = ab, h(2) = ba
このとき,以下の問に答えよ.
(a) h(0120) を求めよ.
(b) h(21120) を求めよ.
(c) L を言語 L(01∗ 2) とするとき,h(L) を表す正規表現を求めよ.
(d) L を言語 L(0 + 12) とするとき,h(L) を表す正規表現を求めよ.
(e) L を言語 {ababa}(一つの文字列 ababa だけから成る言語) とするとき,h−1 (L)
に属するすべての文字列を列挙せよ.
2. アルファベット Σ = {0, 1} からアルファベット T = {a, b} への準同型写像 h を
h(0) = aa,h(1) = bab とする.このとき,言語 L = L((ab + ba)∗ a) に対する
h−1 (L) を表す正規表現を求めよ.
ヒント L を認識する下図の DFA から,h−1 (L) を認識する DFA を構成する (定理
4.16).構成した DFA をもとにして h−1 (L) を求める.
a
q0
a
b
a
b
q2
q1
b
q3
a, b
(裏へ続く)
3. 言語 L と文字 a に対し,wa が L に属すような文字列 w の全体からなる集合を a に関
する L の商といい,L/a と表す.たとえば,L = {a, aab, baa} のとき,L/a = {ε, ba}
である.L が正規言語ならば,L/a も正規言語であることを示したい.以下の証明
の空欄を埋め,証明を完成させよ.
L が正規言語であるとする.このとき,L = L(A) となる DFA A = (Q, Σ, δ, q0 , F )
が存在する.いま,新たな DFA B = (Q, Σ, δ, q0 , F ′ ) を考える.ただし,F ′ =
{q | δ(q, a) = qf , qf ∈ F } とする.このとき,L(B) = L/a であることを以下に
示す.
(a) L(B) ⊆ L/a の証明
w を L(B) に属する任意の文字列とする.w は DFA B で受理されるか
ら,受理の定義より,ある受理状態 qw ∈ F ′ が存在して δ(q0 , w) = qw で
ある.F ′ の構成方法と qw ∈ F ′ であることから,δ(qw , a) = qf を満たす
qf ∈ F が存在する.ここで,文字列 wa について考えると,δ(q0 , wa) =
δ(δ(q0 , w), a) = δ(qw , a) = qf ∈ F となる.すなわち,wa ∈ L(A) = L
であり,商の定義より,w ∈ L/a である.よって,任意の w について,
w ∈ L(B) ならば w ∈ L/a である.
(b) L(B) ⊇ L/a の証明
(a)(b) より,L(B) = L/a が示せた.よって,L/a を認識する DFA B が存在す
ることから,L/a は正規言語である.
4. 言語 L と文字 a に対し,aw が L に属すような文字列 w の全体からなる集合を a\L
と表す.たとえば,L = {a, aab, baa} のとき,a\L = {ε, ab} である.L が正規言語
ならば a\L も正規言語であることを証明せよ.
ヒント:問題 3. および,以下の定理・補題を利用して良い.
定理 4.11 L が正規言語であるとき,その反転 LR も正規言語である.
補題 1 任意の語 w に対して,w = (wR )R .
補題 2 任意の言語 L に対して,L = (LR )R .
2