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

手順1：導出を作る。

生成規則は $S$ を「両端に同じ文字をつけた形」か $c$ に書き換えるので、文字列 $abbcbba$ を外側から順に見ていく。

• 両端が $a$ と $a$ なので、まず $S\to aSa$ を使う。
• 残りの中央 $bbcbb$ の両端は $b$ と $b$ なので $S\to bSb$ を使う。
• さらに残りの中央 $bcb$ の両端も $b$ なので $S\to bSb$ を使う。
• 最後に残った中央 $c$ は $S\to c$ で作る。

したがって導出は
$$S\Rightarrow aSa\Rightarrow abSba\Rightarrow abbSbba\Rightarrow abbcbba$$
となる。各段階で非終端記号は $S$ が 1 つだけなので、これはそのまま最左導出でもある。

手順2：導出木を描く。

生成規則を 1 回使うごとに、書き換えた $S$ の頂点の下に右辺の記号を子として左から順に並べる。

• 根 $S$ の子：$a,S,a$（3 個）
• その中央の $S$ の子：$b,S,b$（3 個）
• その中央の $S$ の子：$b,S,b$（3 個）
• その中央の $S$ の子：$c$（1 個）

葉を左から読むと $abbcbba$ となり、確かに $abbcbba$ になる。

手順3：頂点を数える。

根の $1$ 個に、各規則の適用で増えた子の個数を加えると
$$1+3+3+3+1=11$$
（確認：$S$ のラベルの頂点が $4$ 個、終端記号の葉が文字列の長さと同じ $7$ 個で、$4+7=11$。）

よって頂点の個数は $11$ である。

文字列 $abbcbba$ は長さ 7 で、$S\to aSa$、$S\to bSb$、$S\to bSb$、$S\to c$ の順に導出される。

導出：$S\Rightarrow aSa\Rightarrow abSba\Rightarrow abbSbba\Rightarrow abbcbba$。

この文法は曖昧でなく、各文字列の導出木は一意に定まる。

頂点の数え方：
- 非終端記号 $S$ の頂点は、規則を 4 回適用するので 4 個。
- 葉（終端記号）は、文字列の長さと同じ 7 個。

内訳の確認：
- $S\to aSa$ は子が 3 個（$a$、$S$、$a$）。
- $S\to bSb$ も子が 3 個。
- $S\to c$ は子が 1 個。

$S$ 頂点は 4 個、終端記号の頂点は 7 個なので、合計は $4+7=11$。

検算：根以外の頂点数は子の総数に等しい。子の総数は $3+3+3+1=10$。根を加えて $10+1=11$。

ε を表す頂点はなく、この文法には ε 規則もない。