この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

難易度 2教科書の演習問題レベル証明問題大学数学オートマトン・形式言語

非終端記号 $S$ （開始記号）、終端記号 $a, b$ をもつ文脈自由文法 $G$ の生成規則を
$S \to a S, S \to S b, S \to ε$
の 3 つとする（ $ε$ は空列）。ここで $S$ から終端記号列 $w$ への導出とは、文形式の列 $α_{0} = S \Rightarrow α_{1} \Rightarrow \dots \Rightarrow α_{k} = w$ （ $k$ は正の整数）であって、各 $α_{t - 1} \Rightarrow α_{t}$ が $α_{t - 1}$ の中の 1 つの $S$ を 1 つの生成規則の右辺で置き換えたものであるものをいう。2 つの導出は、文形式の列として異なるとき異なるものと数える。

$m, n$ を 0 以上の整数とする。 $S$ から $a^{m} b^{n}$ への導出の個数がちょうど $(m m + n)$ であることを証明せよ。

この問題で使うもの

文脈自由文法の導出と導出木（説明と入口の問題）

ヒント

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

ヒント 1

導出の途中の文形式がどんな形をしているかを帰納法で調べ、導出と「使う規則の並べ方」とを 1 対 1 に対応させるとよい。

ヒント 2

途中の文形式は常に $a^{i} S b^{j}$ の形で、 $S$ を 1 つだけ含む。したがって各ステップで置き換える位置は一意に決まり、導出は使った規則の列だけで決まる。

ヒント 3

$S \to ε$ を使うと $S$ が消えて導出が終わるので、 $S \to ε$ は最後に 1 回だけ使われる。それより前の各ステップでは $S \to a S$ か $S \to S b$ を使い、最後に $a^{i} b^{j} = a^{m} b^{n}$ となることから使用回数が決まる。

採点の観点と模範解答

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

採点の観点を見る

導出の途中の文形式が $a^{i} S b^{j}$ の形（ $S$ をちょうど 1 つ含む）であることを、ステップ数についての帰納法で示している（3 点）
$S \to ε$ は最後の 1 回だけ使われ、終わりの $a^{i} b^{j} = a^{m} b^{n}$ から $S \to a S$ が $m$ 回、 $S \to S b$ が $n$ 回使われることを導いている（2 点）
導出を、使った規則の列（ $S \to a S$ を $m$ 個、 $S \to S b$ を $n$ 個並べたもの）に対応させ、置き換える位置が一意であることから単射性を示している（2 点）
任意の規則の並べ方から実際に導出が作れること（全射性）を示している（2 点）
並べ方の個数が $(m m + n)$ であることを述べて結論している（1 点）

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

模範解答を読む

補題　導出 $S = α_{0} \Rightarrow α_{1} \Rightarrow \dots \Rightarrow α_{k}$ において、 $α_{t}$ （ $0 \leq t \leq k$ ）が $S$ を含むならば、 $α_{t} = a^{i} S b^{j}$ の形であり、 $i$ は最初の $t$ ステップのうち規則 $S \to a S$ を使った回数、 $j$ は規則 $S \to S b$ を使った回数で、 $i + j = t$ である。

*証明*　 $t$ についての帰納法で示す。 $t = 0$ のとき $α_{0} = S = a^{0} S b^{0}$ で成り立つ。 $α_{t + 1}$ が $S$ を含むとする。 $α_{t + 1}$ は $α_{t}$ の $S$ を置き換えて得られるので $α_{t}$ も $S$ を含み、帰納法の仮定より $α_{t} = a^{i} S b^{j}$ （ $i + j = t$ ）である。 $α_{t}$ の $S$ はこの 1 つだけなので、置き換える位置は一意に決まる。使った規則が $S \to ε$ なら $α_{t + 1} = a^{i} b^{j}$ は $S$ を含まず仮定に反するので、規則は $S \to a S$ か $S \to S b$ であり、それぞれ $α_{t + 1} = a^{i + 1} S b^{j}$ 、 $a^{i} S b^{j + 1}$ となる。どちらも回数の記述と $i + j = t + 1$ を満たす。（補題の証明終わり）

導出の形の決定　 $S$ から $a^{m} b^{n}$ への導出 $α_{0} \Rightarrow \dots \Rightarrow α_{k} = a^{m} b^{n}$ を任意にとる。 $α_{k}$ は $S$ を含まないが $α_{0}$ は含むので、 $S$ を含まない最初の文形式 $α_{s}$ （ $1 \leq s \leq k$ ）がある。 $α_{s}$ は $S$ を含まないので以後どの $S$ も置き換えられず、導出は $α_{s}$ で終わる。すなわち $s = k$ である。補題より $α_{k - 1} = a^{i} S b^{j}$ （ $i + j = k - 1$ ）であり、 $S$ が消えるのは規則 $S \to ε$ を使ったときだけなので $α_{k} = a^{i} b^{j}$ 。 $a^{i} b^{j} = a^{m} b^{n}$ で $a$ の個数と $b$ の個数を比べて $i = m$ , $j = n$ 。よって $k = m + n + 1$ であり、最初の $m + n$ ステップでは $S \to a S$ がちょうど $m$ 回、 $S \to S b$ がちょうど $n$ 回使われ、最後のステップで $S \to ε$ が使われる。

全単射　長さ $m + n$ の列 $(r_{1}, \dots, r_{m + n})$ で、各 $r_{t} \in {S \to a S, S \to S b}$ 、 $S \to a S$ がちょうど $m$ 回現れるもの全体を $P$ とする。導出に、その最初の $m + n$ ステップで使った規則の列を対応させる写像 $Φ$ を考える。上の議論より $Φ$ の値は $P$ に入る。

$Φ$ は単射：補題より各文形式は $S$ を 1 つしか含まないので、使う規則の列を決めると置き換える位置も一意に決まり、 $α_{1}, \dots, α_{m + n}$ が一意に決まる。最後の $α_{m + n + 1}$ も、 $α_{m + n} = a^{m} S b^{n}$ に $S \to ε$ を施した $a^{m} b^{n}$ に決まる。よって規則の列が同じ 2 つの導出は文形式の列として一致する。
$Φ$ は全射：任意の $(r_{1}, \dots, r_{m + n}) \in P$ に対し、 $S$ から始めて $r_{1}, \dots, r_{m + n}$ を順に（各時点でただ 1 つある $S$ に）適用すると、補題の議論と同じく各段階は $a^{i} S b^{j}$ の形を保ち、 $m + n$ ステップ後に $a^{m} S b^{n}$ になる。最後に $S \to ε$ を適用すれば $a^{m} b^{n}$ への導出が得られ、その像は $(r_{1}, \dots, r_{m + n})$ である。

よって $Φ$ は全単射で、導出の個数は $∣ P ∣$ に等しい。 $P$ の元は、 $m + n$ 個の位置のうち $S \to a S$ を置く $m$ 個の位置を選ぶことで一意に定まるので $∣ P ∣ = (m m + n)$ である。

以上より、 $S$ から $a^{m} b^{n}$ への導出の個数はちょうど $(m m + n)$ である。 $■$

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

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題