Graphs and Automata Exercise 12

Graphs and Automata Exercise 12
May 24
1. {0n 12n : n ∈ N} が正則言語でないことを示せ.
2. 正則言語でない集合を挙げ、それが正則言語でないことを示せ.
3. 文脈自由文法 S → 0S11|ϵ (つまり ({S}, {0, 1}, {S → 0S11, S → ϵ}, S)) で生成される言語を求めよ.
4. 文脈自由文法について
(a) 文脈自由文法 S → a, (つまり ({S}, Σ, {S → a}, S), a ∈ Σ) で生成される言語は何か？
(b) 文脈自由文法 S → ϵ, (つまり ({S}, Σ, {S → ϵ}, S)) で生成される言語は何か？
(c) 文脈自由文法 ({S}, Σ, ∅, S) で生成される言語は何か？
(d) A, B ⊂ Σ∗ が文脈自由文法で生成 (こういった列の集合を文脈自由言語という) されるとき, A ∪ B
も文脈自由言語であることを示せ.
(ヒント：L(G) = A, L(G′ ) = B となる文脈自由文法 G = (N, Σ, P, S), G′ = (N ′ , Σ, P ′ , S ′ ) につい
て G′′ = (N ∪ N ′ , Σ, P ∪ P ′ ∪ {T → S, T → S ′ }, T ) で生成される言語は？)
(e) A, B ⊂ Σ∗ が文脈自由言語のとき, AB も文脈自由言語であることを示せ.
(f) A ⊂ Σ∗ が文脈自由言語のとき, A∗ も文脈自由言語であることを示せ.
(g) 正則言語は文脈自由言語であることを示せ.
(ヒント：正則言語を表す正則表現についての帰納法と上の上の小問 1∼6)
5. 文脈自由文法 G = ({A, B, C}, {a, b}, P, S), ただし P を以下の規則からなるものとする.
S → AB | BA | A | B,
A → CAC | a
B → CBC | B
C→a|b
このとき L(G) =∼ {ww : w ∈ {a, b}∗ } となることを示せ.
ヒント： G で生成される列 が
(a) 奇数長さの任意の列
(b) xayubv で |x| = |y|, |u| = |v| となる任意の列
(c) xbyuav で |x| = |y|, |u| = |v| となる任意の列
であることを示し, ww の形とはなりえないこと, さらにそうした任意の列が G で生成されることを示せ.
6. 以下が同値であることを主張する Myhill-Nerode の定理について
I. R は正則言語
II. R の Myhill-Nerode 関係がある
III. ≡R を
def
x ≡R y ↔ ∀z ∈ Σ∗ (xz ∈ R ↔ yz ∈ R)
とすると 同値関係 ≡R の同値類は有限個
について
(a) II→III の証明について, ≡ が R の Myhill-Nerode 関係のとき, 任意の z に対して x ≡ y ならば
xz ≡ yz を |z| についての帰納法で示し, II→III を証明せよ.
(b) III→I の証明について, ≡R から M = (Q, Σ, δ, s, F ) を次で定める.
Q = {[x]≡ : x ∈ Σ∗ }
F = {[x]≡ : x ∈ R},
s = [ϵ]≡ ,
δ([x]≡ , a) = [xa]≡
としたときに ˆ(δ)(a, x) = [x]≡R となることを |x| についての帰納法で示し, III→I を証明せよ.
7. 前回の演習問題 6 の方法で DFA M = (Q, Σ, δ, s, F ) を最小化したものを M≈ = (Q′ , Σ, δ ′ , s′ , F ) として,
DFA N = (R, Σ, ρ, t, G) について, L(M≈ ) = L(N ) と仮定する. また, p ∈ Q に対して, xp を δ(s′ , x) = p
となる x ∈ Σ∗ で辞書式順序で最小のもの, 特に xs′ = ϵ とすると, M に到達不可能な状態がないため,
任意の p ∈ Q′ に対して xp がただひとつ定まる.
このとき, f : Q → R を f (p) = ρ̂(t, xp ) とすると, f が単射である (前回の演習 6f(ii)).
N を同様の方法で最小化した DFA (R′ , Σ, ρ′ , t′ , G′ ) について, g : R′ → Q′ を f と同様の方法で定める
と, 同型写像になることを示せ.
2