computer-science - チョムスキー標準形変換

Question

できるだけ早くあなたの助けが必要です。チョムスキー標準形に変換する必要があります。

S -> 01S | XY

X -> 110Y | 0 | ε

Y -> YY | 1

いくつか試してみましたが、110Y などの混合パーツがあるため、いつも行き詰まります...

Answer 1

少し遅れましたが、できるだけ早く:

開始文法:

S → 01S | XY
X → 110Y | 0 | ε
Y → YY | 1

連結を別々のプロダクションに分割します。

S → 01S
S → XY
X → 110Y
X → 0
X → ε
Y → YY
Y → 1

イプシロンを削除します (インラインX):

S → 01S
S → 110YY
S → 0Y
S → Y
Y → YY
Y → 1

生産を削除S → Y:

S → 01S
S → 110YY
S → 0Y
S → YY
S → 1
Y → YY
Y → 1

すべての端子記号を、右側に記号を持つ新しいプロダクションに置き換えます。

S → ABS
S → BBAYY
S → AY
S → YY
S → 1
Y → YY
Y → 1
A → 0
B → 1

右側に 2 つ以上の非終端記号があるプロダクションをすべて分割します。

S → CS
S → DE
S → AY
S → YY
S → 1
Y → YY
Y → 1
A → 0
B → 1
C → AB
D → BB
E → AF
F → YY

その後、完了です。