解答例

オートマトン・形式言語演習問題解答
2015 年 12 月 1 日分
1. (a) x = a, y = b, z = a と x = ǫ, y = a, z = ba．
(b) x = a, y = b, z = ǫ と x = ǫ, y = a, z = b．
(c) x = ǫ, y = bb, z = aba と x = bb, y = a, z = ba．
2. (a) L1 は正規言語である． L1 を表す正規表現は 0∗ 1∗ ．
(b) L2 は正規言語ではない．このことを背理法を用いて示す．
L2 が正規言語であると仮定する．
仮定と反復補題より，正整数 n が存在して， |w| ≥ n であるすべての w ∈ L2 について， (1)∼ (3)
を満たす分割 w = xyz が存在する．
(1) y 6= ǫ,
(2) |xy| ≤ n,
(3) すべての k ≥ 0 について xy k z ∈ L2 ．
ここで， w = 0n 1n を L2 から選択する． |w| = 2n ≥ n であるので， (1)∼ (3) を満たす分割
w = xyz が存在する． (1) と (2) を満たすことから， 0 < m ≤ n であるような m が存在して
y = 0m である．さらに，条件 (3) を満たすことから， xy 2 z = 0n+m 1n ∈ L2 となる．しかし，
n + m > n であるので xy 2 z ∈
/ L2 である．よって，矛盾する．
(c) L3 は正規言語である． L3 を表す正規表現は (00)∗ ．
(d) L4 は正規言語でない．このことを背理法を用いて示す．
L4 が正規言語であると仮定する．
仮定と反復補題より，正整数 n が存在して， |w| ≥ n であるすべての w ∈ L4 について， (1)∼ (3)
を満たすような分割 w = xyz が存在する．
(1) y 6= ǫ,
(2) |xy| ≤ n,
(3) すべての k ≥ 0 について xy k z ∈ L4 ．
2
w = 0n を L4 から選択する． |w| = n2 ≥ n であるので， (1)∼ (3) を満たすように分割 w = xyz
が可能である．条件 (3) より xy 2 z ∈ L4 である．しかし，条件 (1) と (2) より，
n2 = |w| = |xyz| < |xy 2 z|
≤ n2 + n
< (n + 1)2
すなわち，以下が成り立つ．
n2 < |xy 2 z| < (n + 1)2
長さが平方数ではないので， xy 2 z 6∈ L4 である．よって，矛盾する．
3. L(M2 ) の補集合を認識する DFA M2′ を構成し， L(M1 ) ∩ L(M2′ )(= L(M1 ) − L(M2 )) を認識する DFA
Ma を M1 と M2′ から構成する． Ma の状態遷移図は以下の通りである．

Download Report