compiler-construction - 線形文法を有限状態マシンに変換する方法

Question

線形の正しい文法を有限状態機械に変換する必要があります。文法は

S —> bA|aD|bC
А —> aC|bA
C —> bB|aA|b
B —> aD|bC|a
D —> aA|aC

通常、問題は次のように解決されます。各状態に非終端を関連付けます。状態とによって X から Y への遷移がある場合、ルール X → aY を追加します。最終状態規則 X → ε を追加します。ε遷移の場合 - X → Y.

例えば：

A → aB | cC
B → bD | cE
C → ε
D → aB | cC
E → aB | cC

質問。

1. 接続AとAがある場合の方法、たとえばA -> aC | ば。
2. 構造 C -> bB の扱い方 | ああ | b、最後は b だけです。

Answer 1

1] 自己ループを作成できます (たとえば、ノード Z に文字 o を追加してからノード Z に移動できます)。

2]トラップ状態を使用します。そこからどこにも移動することはできませんが、そこにたどり着くには移動が必要です (つまり、文字が必要です)。