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

オートマトン・形式言語演習問題解答例
2014 年 12 月 2 日分
1. (a) aabbaa
(b) baababbaa
(c) a(ab)∗ ba
(d) a + abba
(e) 110, 022, 102
2. 与えられた言語 L を認識する DFA から，h−1 (L) を認識する DFA を構成すると，下図のようになる．
この DFA が認識する言語を正規表現で表すと，(101)∗ 10 もしくは 10(110)∗ となる．
1
q0
q1
0
0
1
0
q2
1
q3
0,1
3. 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 の証明 (* 問題はこの部分 *)
w を L/a に属する任意の文字列とする．商の定義より，wa ∈ L = L(A) である．すなわち，ある受
理状態 qf ∈ F が存在して，δ(q0 , wa) = δ(δ(q0 , w), a) = qf ．ここで，q ′ = δ(q0 , w) とおく．この
とき，δ(q ′ , a) = qf ∈ F であるから，F ′ の構成法から q ′ ∈ F ′ である．つまり，δ(q0 , w) = q ′ ∈ F ′
となり，w は DFA B で受理される．よって，任意の w について，w ∈ L/a ならば w ∈ L(B) で
ある．
(a)(b) より，L(B) = L/a が示せた．よって，L/a を認識する DFA B が存在することから，L/a は
正規言語である．
1
4. L を正規言語とすると，定理 4.11 より，その反転 LR も正規言語である．また，LR が正規言語であ
るならば，問題 3. より，その商である LR /a も正規言語である．また，LR /a が正規言語であるとき，
その反転 (LR /a)R も正規言語である．ここで，(LR /a)R = a\L であることを示せば，a\L が正規言
語であることを示すのに充分である．
任意の w について，w ∈ (LR /a)R であるときかつそのときに限り w ∈ a\L であることを示す．
w ∈ (LR /a)R
⇔ wR ∈ ((LR /a)R )R = LR /a 反転の定義および補題 2 より
⇔ wR a ∈ LR
商の定義より
⇔ aw = (wR a)R ∈ (LR )R = L 反転の定義および補題 1,2 より
⇔ w ∈ a\L
a\L の定義より
よって，(LR /a)R = a\L である．以上により，L が正規言語であるとき，a\L も正規言語であること
が示せた．
(別解):
L が正規言語であるとする．このとき，L = L(A) となる DFA A = (Q, Σ, δ, q0 , F ) が存在する．い
ま，新たな DFA A′ = (Q, Σ, δ, q0′ , F ) を考える．ここで，q0′ = δ(q0 , a) とする．A は DFA であるか
ら，q0′ は一意に定まる．このとき，L(A′ ) = a\L であることを以下に示す．
(a) L(A′ ) ⊆ a\L の証明
いま，w ∈ L(A′ ) となる任意の w について考える．DFA A′ で受理されるから，ある受理状態
qf ∈ F が存在して，δ(q0′ , w) = qf である．ここで，q0′ = δ(q0 , a) であるから，δ(δ(q0 , a), w) =
qf ∈ F である．そして δ(δ(q0 , a), w) = δ(q0 , aw) となるから，δ(q0 , aw) = qf ∈ F である．す
なわち，aw ∈ L(A) である．a\L の定義より，w ∈ a\L である．よって，任意の w について，
w ∈ L(A′ ) ならば w ∈ a\L である．
(b) a\L ⊆ L(A′ ) の証明
いま，w ∈ a\L となる任意の w について考える．a\L の定義より，aw ∈ L = L(A)．すなわち，あ
る受理状態 qf ∈ F が存在して，δ(q0 , aw) = qf である．さらに，δ(q0 , aw) = δ(δ(q0 , a), w) = qf ．
ここで，q0′ = δ(q0 , a) であるから，δ(q0′ , w) = qf ∈ F ．よって，w は DFA A′ で受理される．以
上のことから，任意の w について，w ∈ a\L ならば，w ∈ L(A′ ) である．
(a)(b) より，L(A′ ) = a\L が示せた．よって，a\L を受理する DFA A′ が存在することから，a\L は
正規言語である．
追加問題
教科書 p.166 問 4.2.13 (b)
L = {0 1 2
| n ≥ m ≥ 0} とおく．L0i1j = L(0∗ 1∗ ) とおくと，L0i1j は正規言語である．このと
き，L0n1n = {0n 1n | n ≥ 0} = L ∩ L0i1j が成り立つ．L0n1n が正規言語ではないことと，積集合演
n m n−m
算は正則性を保存する（L1 と L2 が正規言語であるならば L1 ∩ L2 も正規言語である）ことより，L
は正規言語ではない．
（もし L が正規言語であれば，L0n1n も正規言語でなければならない．
）
2

Download Report