オートマトン・形式言語の問題

難易度 3期末試験の応用レベル証明問題大学数学オートマトン・形式言語

アルファベット $Σ = {a, b}$ 上の正規表現を考える。正規表現 $r$ が表す言語を $L (r)$ と書き、 $L (r + s) = L (r) \cup L (s)$ 、 $L (r s) = L (r) L (s)$ （連接）、 $L (r^{*}) = ⋃_{m \geq 0} L (r)^{m}$ （ $L (r)^{0} = {ε}$ 、 $ε$ は空列）と定める。文字列 $w \in Σ^{*}$ に含まれる文字 $a$ の個数を $∣ w ∣_{a}$ 、 $w$ の長さを $∣ w ∣$ と書く。

正規表現
$R = (b + a b^{*} a)^{*}$
について、
$L (R) = {w \in Σ^{*} ∣ ∣ w ∣_{a} は偶数}$
が成り立つことを証明せよ。

この問題で使うもの

正規表現が表す言語と文字列の判定（説明と入口の問題）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

集合の等式なので、 $L (R) \subseteq E$ と $E \subseteq L (R)$ の 2 つの包含を示す。前者は $X^{m}$ の $m$ についての帰納法、後者は文字列の長さについての帰納法が使える。

ヒント 2

$X = L (b + a b^{*} a)$ の元 $b$ と $a b^{k} a$ は、どれも $a$ を偶数個（ $0$ 個か $2$ 個）含む。また $x \in X$ , $y \in X^{*}$ なら $x y \in X^{*}$ である。

ヒント 3

$E \subseteq L (R)$ では $w$ の先頭の文字で場合分けする。先頭が $a$ のときは、残りの部分に $a$ が奇数個あるので必ず次の $a$ があり、 $w = (a b^{k} a) w^{''}$ と分解できる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$L (R) = X^{*} = ⋃_{m} X^{m}$ （ $X = {b} \cup {a b^{k} a}$ ）と書き直し、2 つの包含に分けて示す方針を立てている（1 点）
$X$ の各元の $a$ の個数が偶数であることと $∣ uv ∣_{a} = ∣ u ∣_{a} + ∣ v ∣_{a}$ から、 $m$ についての帰納法で $X^{m} \subseteq E$ を示している（3 点）
$E \subseteq L (R)$ を長さについての（累積）帰納法で示す枠組みを立て、空列の場合を処理し、 $x \in X, y \in X^{*} \Rightarrow x y \in X^{*}$ を用いている（2 点）
先頭が $b$ の場合に $w = b w^{'}$ として $w^{'} \in E$ に帰着させている（1 点）
先頭が $a$ の場合に、残りの $a$ の個数が奇数であることから次の $a$ の存在を示し、 $w = (a b^{k} a) w^{''}$ と分解して $w^{''} \in E$ に帰着させている（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

$X = L (b + a b^{*} a) = {b} \cup {a b^{k} a ∣ k は 0 以上の整数}$ 、 $E = {w \in Σ^{*} ∣ ∣ w ∣_{a} は偶数}$ とおく。 $L (R) = X^{*} = ⋃_{m \geq 0} X^{m}$ である。 $∣ uv ∣_{a} = ∣ u ∣_{a} + ∣ v ∣_{a}$ がすべての $u, v \in Σ^{*}$ で成り立つことを用いる。

(1) $L (R) \subseteq E$ の証明　0 以上の整数 $m$ について「 $X^{m} \subseteq E$ 」を $m$ についての帰納法で示す。

$m = 0$ ： $X^{0} = {ε}$ で $∣ ε ∣_{a} = 0$ は偶数なので成り立つ。
$X^{m} \subseteq E$ を仮定する。 $X^{m + 1} = X^{m} X$ の元は $uv$ （ $u \in X^{m}$ , $v \in X$ ）と書ける。仮定より $∣ u ∣_{a}$ は偶数であり、 $v = b$ なら $∣ v ∣_{a} = 0$ 、 $v = a b^{k} a$ なら $∣ v ∣_{a} = 2$ なので $∣ v ∣_{a}$ も偶数である。よって $∣ uv ∣_{a} = ∣ u ∣_{a} + ∣ v ∣_{a}$ は偶数で、 $uv \in E$ 。したがって $X^{m + 1} \subseteq E$ 。

よって $L (R) = ⋃_{m \geq 0} X^{m} \subseteq E$ 。

(2) $E \subseteq L (R)$ の証明　まず、 $x \in X$ と $y \in X^{*}$ に対し $x y \in X^{*}$ であることを確認する。 $y \in X^{m}$ となる $m$ をとると、 $x y \in X X^{m} = X^{m + 1} \subseteq X^{*}$ だからである（ $X X^{m} = X^{m + 1}$ は連接の結合法則による）。

0 以上の整数 $ℓ$ について「長さ $ℓ$ の $E$ の元はすべて $X^{*}$ に属する」を、 $ℓ$ についての累積帰納法で示す。すなわち、長さが $ℓ$ 未満の $E$ の元がすべて $X^{*}$ に属すると仮定して、 $∣ w ∣ = ℓ$ , $w \in E$ なら $w \in X^{*}$ を示す。

$ℓ = 0$ のとき： $w = ε \in X^{0} \subseteq X^{*}$ 。
$ℓ \geq 1$ のとき： $w$ の先頭の文字で場合分けする。
先頭が $b$ のとき： $w = b w^{'}$ と書ける。 $∣ w^{'} ∣_{a} = ∣ w ∣_{a}$ は偶数なので $w^{'} \in E$ で、 $∣ w^{'} ∣ = ℓ - 1 < ℓ$ だから仮定より $w^{'} \in X^{*}$ 。 $b \in X$ なので、上の確認から $w = b w^{'} \in X^{*}$ 。
先頭が $a$ のとき： $w = a v$ と書ける。 $∣ v ∣_{a} = ∣ w ∣_{a} - 1$ は奇数なので $∣ v ∣_{a} \geq 1$ であり、 $v$ は $a$ を含む。 $v$ に現れる最初の $a$ の位置で区切ると、0 以上の整数 $k$ と $w^{''} \in Σ^{*}$ を用いて $v = b^{k} a w^{''}$ と書ける（最初の $a$ より前はすべて $b$ だから）。すると $w = (a b^{k} a) w^{''}$ であり、 $∣ w^{''} ∣_{a} = ∣ w ∣_{a} - 2$ は偶数なので $w^{''} \in E$ 、また $∣ w^{''} ∣ = ℓ - k - 2 < ℓ$ なので仮定より $w^{''} \in X^{*}$ 。 $a b^{k} a \in X$ なので $w \in X^{*}$ 。

先頭の文字は $a$ か $b$ のどちらかなので、場合分けに漏れはない。よってすべての $ℓ$ について主張が成り立ち、 $E \subseteq X^{*} = L (R)$ 。

(1), (2) より $L (R) = E$ 、すなわち $L ((b + a b^{*} a)^{*}) = {w \in Σ^{*} ∣ ∣ w ∣_{a} は偶数}$ である。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる