Typ-2 Grammatik in Chomsky Normalform

Question

Frage:

Sei \( G=(V, \Sigma, P, S) \) eine Typ-2 Grammatik mit Alphabet \( \Sigma=\{a, b, c\} \), Variablen \( V= \) \( \{S, B, C, D\} \) und Regeln
\( \begin{aligned} P=\{S & \rightarrow a C B b \mid \lambda, \\ B & \rightarrow B D|B c| b c \mid C, \\ C & \rightarrow a C c|c c| D, \\ D & \rightarrow a B b|B b D| b\} \end{aligned} \)
Sei \( L(G) \) die von \( G \) erzeugte Sprache.
1. Erstellen Sie eine Grammatik \( G^{\prime} \) in Chomsky-Normalform, so dass \( L(G)=L\left(G^{\prime}\right) \).

Answer 1

Um eine Grammatik in Chomsky-Normalform zu bringen, müssen alle Regeln die Form haben A → BC oder A → a, wo A, B, C in V sind und a in Σ.

Eine Möglichkeit, die Grammatik G in Chomsky-Normalform zu bringen, ist folgende:

\( P^{\prime} = \begin{aligned} S & \rightarrow a E B b \mid \lambda, \\ E & \rightarrow C F, \\ F & \rightarrow B G|c, \\ G & \rightarrow D H|c, \\ H & \rightarrow c, \\ B & \rightarrow b, \\ C & \rightarrow c, \\ D & \rightarrow b \end{aligned} \)

Beachten Sie, dass die Regel \( S \to \lambda \) nicht unbedingt geändert werden muss, da sie bereits die erforderliche Form hat.

Es ist zu beachten, dass die resultierende Grammatik G' in Chomsky-Normalform ist und dass L(G) = L(G').