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

オートマトン・形式言語 演習問題
2016 年 11 月 29 日
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) を求める．
(裏へ続く)
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