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

方針　開始記号 $S$ から、いちばん左の非終端記号を 1 つずつ生成規則で書き換えて $w=aabbbcc$ をつくる（最左導出）。書き換えるたびに 1 ステップと数える。

どの規則を使うかの決め方　この文法の文形式には、非終端記号がいつもちょうど 1 個しかない。また、つくりたい文字列を見ればどの規則を使うかが 1 通りに決まる。
- $S$ を書き換えるとき、まだ外側に $a\cdots c$ をつける必要があれば $S\to aSc$ を、そうでなければ $S\to T$ を使う。
- $T$ を書き換えるとき、まだ $b$ を続ける必要があれば $T\to bT$ を、最後の $b$ なら $T\to b$ を使う。

$w=aabbbcc$ は「$a$ が 2 個、$b$ が 3 個、$c$ が 2 個」なので、次のように導出できる。
$$\begin{array}{rlrl}S& \Rightarrow aSc& & (S\to aSc)\\ & \Rightarrow aaScc& & (S\to aSc)\\ & \Rightarrow aaTcc& & (S\to T)\\ & \Rightarrow aabTcc& & (T\to bT)\\ & \Rightarrow aabbTcc& & (T\to bT)\\ & \Rightarrow aabbbcc& & (T\to b)\end{array}$$

導出木との対応　この導出を導出木で表すと、根 $S$ の子が $a,S,c$、その $S$ の子が $a,S,c$、その $S$ の子が $T$、その $T$ の子が $b,T$、さらにその $T$ の子が $b,T$、最後の $T$ の子が $b$ となる。葉を左から読むと $aabbbcc$ になり、$w$ が $G$ で生成されることが確かめられる。導出木の内部節点（非終端記号の節点）は $S,S,S,T,T,T$ の 6 個で、これは規則を適用した回数と一致する。

よって、生成規則を適用する回数は $6$ 回である。

文法 $G$ は $S\to aSc\mid T$、$T\to bT\mid b$ である。$w=aabbbcc$ を導出する。

$a$ が 2 個、$c$ が 2 個あるので、$S\to aSc$ を 2 回適用する。その後 $S\to T$ を 1 回適用する。
$T$ から $bbb$ を得るには、$T\to bT$ を 2 回、$T\to b$ を 1 回適用する。

最左導出（各段階で非終端記号は 1 個しかないので導出は一意）:
$S\Rightarrow aSc\Rightarrow aaScc\Rightarrow aaTcc\Rightarrow aabTcc\Rightarrow aabbTcc\Rightarrow aabbbcc$

適用した規則を数える。$S\to aSc$ が 2 回、$S\to T$ が 1 回、$T\to bT$ が 2 回、$T\to b$ が 1 回で、合計 $2+1+2+1=6$ 回。

検算: 導出の各行で文字列が変化するのは 6 回で、上の矢印も 6 本である。また、各段階で非終端記号が 1 個だけなので、導出は一意に決まる。よって 6 ステップである。