非終端記号 S, A、終端記号 a, b、開始記号 S からなる正規文法で、生成規則が S → aS、S → bA、A → a のとき、この文法が生成する言語を表す正規表現はどれか。

解説

正解は「a*ba」です。S → aS を0回以上適用すると、先頭に a が任意個並びます。その後 S → bA で b を出力して A に移り、A → a で a を1つ出力して終わります。したがって生成される文字列は ba、aba、aaba、… で、正規表現 a*ba で表せます。非終端記号を状態、規則 S → aS を「S から a で S へ遷移」とみなせば、同じ言語を受理する NFA に翻訳できます。「(ab)*a」は ab の繰返しの後に a が続く形で、ba を表せません。「a*b*a」は b を複数含む abba なども表しますが、この文法では b はちょうど1個です。「ba*」は末尾の a が任意個で、先頭の a を表せません。