正規表現が表す言語と文字列の判定

和 $+$ ・連接・クリーネ閉包 $^{*}$ からなる正規表現 $r$ の言語 $L (r)$ を読み取り、与えられた文字列が $L (r)$ に属するかを判定でき、2 つの正規表現が同じ言語を表すかを判断できる

前提

中学までに習ったことだけで始められます。

説明

正規表現は、文字列の集まり（言語）を $+$ ・連接・ $^{*}$ の 3 つの操作だけで短く書き表す方法です。この技能を身につけると、正規表現 $r$ を見てそれが表す言語 $L (r)$ を言葉で説明できます。また、与えられた文字列が $L (r)$ に入るかを判定でき、2 つの正規表現が同じ言語を表すかどうかも判断できます。テキスト検索のパターン、字句解析、オートマトンの設計などで使います。

なぜそうしてよいのか

文字の有限集合 $Σ$ （アルファベット）を決めます。 $Σ$ の文字を有限個（0 個でもよい）並べたものを文字列といい、長さ 0 の文字列を $ε$ と書きます。文字列の集合を言語といいます。正規表現と、それが表す言語 $L (r)$ は、小さい部品から順に次のように定めます。各文字 $a \in Σ$ について $L (a) = {a}$ 、 $L (ε) = {ε}$ 、 $L (\emptyset) = \emptyset$ です。正規表現 $r, s$ に対しては次のように定めます。
・和： $L (r + s) = L (r) \cup L (s)$ （どちらかに合う）
・連接： $L (r s) = {x y ∣ x \in L (r), y \in L (s)}$ （前半が $r$ 、後半が $s$ に合うように切れる）
・閉包： $L (r^{*}) = {ε} \cup L (r) \cup L (r r) \cup L (r r r) \cup \dots$ （ $r$ に合う断片を 0 個以上つなげたもの）
演算の強さは $^{*}$ ＞連接＞ $+$ の順です。たとえば $a b^{*} + c$ は $(a (b^{*})) + c$ と読みます。

このように $L (r)$ は部品の言語から組み立てられています。そのため「文字列 $w$ が $L (r)$ に入るか」という問いは、部品についての小さな問いに分解できます。たとえば $w \in L (r s)$ を調べるには、 $w$ を前後 2 つに切る方法（有限通り）を試し、前が $L (r)$ 、後ろが $L (s)$ に入る切り方があるかを見ればよいです。 $w \in L (r^{*})$ なら、 $w$ を $L (r)$ の要素の断片に区切れるかを見ます。 $w = ε$ ならいつでも入ります。

2 つの正規表現 $r, s$ が同じ言語を表す（ $L (r) = L (s)$ ）とは、集合として等しいこと、つまり $L (r) \subseteq L (s)$ と $L (s) \subseteq L (r)$ の両方が成り立つことです。等しくないことを示すには、一方にだけ入る文字列を 1 つ挙げれば十分です。等しいことを示すには、それぞれの言語を言葉で特徴づけ（例：「 $a, b$ からなる任意の文字列」）、両方の包含を確かめます。

手順

正規表現に括弧を補い、構造をはっきりさせる（優先順位は $^{*}$ ＞連接＞ $+$ ）。例： $a b^{*} + b = (a (b^{*})) + b$
内側の部品から順に言語を読み取り、 $L (r)$ を言葉で特徴づける（例： $L ((a + b)^{*})$ は $a, b$ からなるすべての文字列で、 $ε$ も含む）
判定する文字列 $w$ について、外側の演算に合わせて調べる。 $+$ ならどちらかに入るか、連接なら前後に切れるか、 $^{*}$ なら $L (r)$ の断片に区切れるかを見る
区切り方が 1 通りも見つからないときは、その理由を示す（例：「どの断片も $b$ で終わるのに、 $w$ は $a$ で終わる」）。その上で $w \in / L (r)$ と結論する
2 つの正規表現の比較では、まず短い文字列を順に試して、一方にだけ入る反例を探す。反例があれば等しくない。見つからなければ両方の言語を言葉で特徴づけ、 $L (r) \subseteq L (s)$ と $L (s) \subseteq L (r)$ を確かめる

例題

アルファベット $Σ = {a, b}$ 上の正規表現 $r = (ab + b)^{*}$ について、次の文字列のうち $L (r)$ に属するものをすべて選べ。
ア： $abab$ 　イ： $aab$ 　ウ： $babb$ 　エ： $abba$

例題の解答

手順 1： $r$ は $(ab + b)$ 全体に $^{*}$ がかかった形です。中の $ab + b$ は「 $ab$ または $b$ 」と読みます。
手順 2： $L (ab + b) = {ab, b}$ です。したがって $L (r)$ は、断片 $ab$ と $b$ を好きな順に 0 個以上つなげた文字列全体になります（ $ε$ も含む）。どちらの断片も $b$ で終わり、 $a$ の直後には必ず $b$ が来ます。
手順 3（判定）：
ア $abab = ab \cdot ab$ と区切れるので、属します。
イ $aab$ ：先頭の $a$ で始まる断片は $ab$ しかありません。ところが 2 文字目は $a$ です。 $a$ の直後が $b$ でないので区切れず、属しません。
ウ $babb = b \cdot ab \cdot b$ と区切れるので、属します。
エ $abba$ ：どの断片も $b$ で終わるので、空でない $L (r)$ の要素は必ず $b$ で終わります。 $abba$ は $a$ で終わるので、属しません（手順 4）。
よって、属するのはアとウです。

答え:

ア, ウ

よくある誤り

$a b^{*}$ を $(ab)^{*}$ と読んでしまう誤り。正しくは $^{*}$ は直前の 1 文字（または括弧のまとまり）だけにかかり、 $a b^{*} = a (b^{*})$ である。 $abab \in / L (a b^{*})$ だが、 $abab \in L ((ab)^{*})$ 。
$(ab)^{*}$ と $a^{*} b^{*}$ を同じ言語だと思ってしまう誤り。正しくは $aabb \in L (a^{*} b^{*})$ だが、 $aabb \in / L ((ab)^{*})$ である。逆に $abab \in L ((ab)^{*})$ だが、 $abab \in / L (a^{*} b^{*})$ 。
$(a + b)^{*} = a^{*} + b^{*}$ としてしまう誤り。正しくは $(a + b)^{*}$ では断片ごとに $a$ か $b$ を選び直せるので、 $ab \in L ((a + b)^{*})$ である。一方 $a^{*} + b^{*}$ は「 $a$ だけ」か「 $b$ だけ」の列なので、 $ab \in / L (a^{*} + b^{*})$ 。
$r^{*}$ に空文字列が入ることを忘れる誤り。正しくは繰り返し 0 回を含むので、どんな $r$ でも $ε \in L (r^{*})$ である（ $L (\emptyset^{*}) = {ε}$ でもある）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（教科書の例題レベル）
アルファベット ${a, b}$ 上の正規表現
$r = a^{*} b a^{*}$
を考える。次の文字列のうち、 $r$ が表す言語 $L (r)$ に属するものをすべて選べ。
ア: $b$
イ: $aab$
ウ: $abab$
エ: $baa$
オ: $aa$

この技能を使う問題

難易度 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} は偶数}$
が成り立つことを証明せよ。

この技能の次に学べること

正規言語に属する長さ n の文字列の数え上げ（大学数学オートマトン・形式言語）