生成規則 S → aSb、S → ab をもつ文法で、開始記号 S から記号列 aaaabbbb を導出するのに必要な規則の適用回数はいくつか。

解説

正解は「4」です。S → aSb を1回適用するごとに外側に a と b が1つずつ加わり、最後に S → ab で中央の ab を生成して終わります。aaaabbbb は a と b が4個ずつなので、S → aSb を3回適用して aaaSbbb とし、S → ab を1回適用して完成します。合計4回です。この文法が生成する言語は $\{a^n{b}^n\mid n\geqq 1\}$ で、$a^n{b}^n$ の導出には常に n 回の適用が必要です。「3」は S → aSb の回数だけを数え、最後の S → ab を数え忘れています。「5」は S → aSb を4回適用したと考えた場合で、a と b が5個ずつになってしまいます。「8」は文字数をそのまま適用回数とみなした誤りです。