オ ート マト ン 理論演習問題解答例
2016 年 1 月 26 日分
1. (a) CFG G = ({S, T }, {a, b, c}, P, S)
P = {S → aSc | T, T → bT c | ε}
(b) P = ({q0 }, {a, b, c}, {a, b, c, S, T }, δ, q0, S) (空ス タ ッ ク に よ る 受理)
δ(q0 , ε, S)
=
{(q0 , aSc), (q0 , T )}
δ(q0 , ε, T ) =
{(q0 , bT c), (q0 , ε)}
δ(q0 , a, a)
δ(q0 , b, b)
=
=
{(q0 , ε)}
{(q0 , ε)}
δ(q0 , c, c)
=
{(q0 , ε)}
2. オート マ ト ン :
(a)
(c)
(b)
(d)
正規表現
(a) ǫ + 0∗ 1 + 1∗ 0 な ど
(b) (011 + 1)∗ な ど
(c) (0 + 1)∗ 1(ǫ + 0)(ǫ + 0) な ど
(d) 1∗ + 1∗ 01∗ + 1∗ 01∗ 01∗ な ど
3. L5 を 認識する DFA M5 と h−1 (L5 ) を 認識する DFA M5′ は以下の通り であ る ．
(b) M5′
(a) M5
L(M5′ ) を 表現する 正規表現は (0∗ 1)+ ， (0 + 1)∗ 1 な ど
1
4. L6 が正規言語であ る と 仮定する ． 仮定と 反復補題よ り ， 正整数 n が存在し て ， |w| ≥ n であ
る すべて の w ∈ L6 に ついて ， (1)∼ (3) を 満た す分割 w = xyz が存在する ．
(1) y 6= ǫ,
(2) |xy| ≤ n,
(3) すべて の k ≥ 0 に ついて xy k z ∈ L2 ．
以上の n に 対し て w = 0n 110n ∈ L6 を 選択する ． |u| = 2n + 2 ≥ n であ る ので， (1)∼ (3) を
満た す分割 u = xyz が存在する ． (1) と (2) を 満た すこ と から ， 0 < m ≤ n であ る よ う な m
が存在し て y = 0m であ る ． さ ら に ， 条件 (3) を 満た すこ と から ， xz = 0n−m 110n ∈ L6 で
あ る ． し かし ， n − m 6= n であ る ので xz ∈
/ L6 であ る ． よ っ て ， 矛盾する ．
補足: w = 02n な ど のよ う に 0 のみ（ あ る いは 1 のみ） から な る 系列を 選ぶと ， xz の長さ が
偶数であ る 場合に xz ∈
/ L6 を 示せな い．
2
© Copyright 2024 ExpyDoc
