オ ート マト ン ・ 形式言語 演習問題
2015 年 12 月 8 日
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
© Copyright 2024 ExpyDoc
