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

難易度 1教科書の例題レベル大学数学オートマトン・形式言語

アルファベット ${a, b}$ 上の正規表現
$r = a^{*} b a^{*}$
を考える。次の文字列のうち、 $r$ が表す言語 $L (r)$ に属するものをすべて選べ。

ア: $b$

イ: $aab$

ウ: $abab$

エ: $baa$

オ: $aa$

この問題で使うもの

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

ヒント

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

ヒント 1

正規表現が表す言語を読み取る技能を使います。 $a^{*}$ と $b$ がそれぞれどんな文字列を表すかを考え、連接でつなぐとどうなるかを調べましょう。

ヒント 2

$a^{*}$ は「 $a$ を 0 回以上」なので、 $L (r) = {a^{m} b a^{n} ∣ m, n \geq 0}$ と書けます。これは $b$ を何個含む文字列でしょうか。

ヒント 3

$L (r)$ は「 $b$ をちょうど 1 個含む文字列」全体です。各選択肢に含まれる $b$ の個数を数えてみましょう。

答えと解説

答えを見る

ア, イ, エ

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

解説を読む

手順 1: 正規表現の各部分が表す言語を読み取る。

$a^{*}$ は $a$ を 0 回以上並べた文字列全体 ${ε, a, aa, aaa, \dots}$ を表す（ $ε$ は空文字列）。 $b$ は 1 文字の $b$ だけを表す。

手順 2: 連接の意味を使って $L (r)$ を言い換える。

$r = a^{*} b a^{*}$ は「 $a$ を 0 個以上」「 $b$ を 1 個」「 $a$ を 0 個以上」をこの順につないだものなので、
$L (r) = {a^{m} b a^{n} ∣ m, n は 0 以上の整数}$
である。つまり $L (r)$ は「 $b$ をちょうど 1 個だけ含む文字列」全体である。

手順 3: 各文字列を判定する。

ア $b$ : $m = 0, n = 0$ とすれば $a^{0} b a^{0} = b$ 。属する。
イ $aab$ : $m = 2, n = 0$ とすれば $a^{2} b a^{0} = aab$ 。属する。
ウ $abab$ : $b$ を 2 個含むので、 $b$ がちょうど 1 個の形にできない。属さない。
エ $baa$ : $m = 0, n = 2$ とすれば $a^{0} b a^{2} = baa$ 。属する。
オ $aa$ : $b$ を 1 個も含まないので、真ん中の $b$ に対応する文字がない。属さない。

よって、 $L (r)$ に属するのはア, イ, エである。

別解

r = a*ba* は b をちょうど 1 個含み、その前後に a が 0 個以上並ぶ文字列を表す。ア b: a が 0 個ずつで属する。イ aab: 属する。ウ abab: b が 2 個なので属さない。エ baa: 属する。オ aa: b を含まないので属さない。よってア, イ, エ。

この問題の確認

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

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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

状態	入力 $0$	入力 $1$
$A$	$B$	$A$
$B$	$C$	$A$
$C$	$C$	$B$

状態	入力 $0$	入力 $1$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{0}$	$q_{2}$
$q_{2}$	$q_{2}$	$q_{2}$