Grammatiken < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 13:05 Mo 27.12.2004 | | Autor: | Karl_Pech |
Hi Leute,
Ich habe versucht die Grammatik [m]G = \left( {V,\;\Sigma ,\;P,\;S} \right)[/m] mit
[m]\begin{gathered}
V = \left\{ {E,\;T,\;F} \right\},\;\Sigma = \left\{ {\star,\; + ,\;(,\;),\;a} \right\},\; \hfill \\
P = \left\{ {E \to E + T\; |\; T,\;T \to T \star F\; |\; F,\;F \to \left( E \right)\; |\; a} \right\} \hfill \\
\end{gathered}[/m]
und S = E in CNF umzuformen:
Schritt 1: (Eliminieren von Produktionen der Form [m]A \to B\quad \forall A,B \in V[/m]):
Wir eliminieren die Produktion $T [mm] \to [/mm] F$ mit $F [mm] \to \left( E \right)\; |\; [/mm] a$ und erhalten
[m]P_1 = \left\{ {E \to E + T\; |\; T,\;T \to T\star\left( E \right)\; |\; T\star a\; |\; \left( E \right)\; |\; a} \right\}[/m].
Es gilt [mm] $V_1 [/mm] : = V - [mm] \left\{ F \right\}$.
[/mm]
Wir eliminieren die Produktion $E [mm] \to [/mm] T$ mit
[m]T \to T\star\left( E \right)\; |\; T\star a\; |\; \left( E \right)\; |\; a[/m]
und erhalten
[m]\begin{gathered}
P_2 = \left\{ {E \to E + T\; |\; T\star\left( E \right)\; |\; T\star a\; |\; \left( E \right)\; |\; a,\;} \right. \hfill \\
\left. {T \to T\star\left( E \right)\; |\; T\star a\; |\; \left( E \right)\; |\; a} \right\} \hfill \\
\end{gathered}[/m].
Schritt 2: (Alle Produktionen, die nicht die Form [m]A \to a\quad \forall A \in V_1 \forall a \in \Sigma[/m] haben, auf die Form [m]A \to BC\quad \forall A,B,C \in V_1[/m] bringen):
Wir ersetzen zuerst alle Terminale der betroffenen Produktionen:
[m]\begin{gathered}
P_3 = \left\{ {E \to EX_ + T\; |\; TX_ \star X_( EX_) \; |\; TX_ \star X_a \; |\; X_( EX_) \; |\; a,\;} \right. \hfill \\
T \to TX_ \star X_( EX_) \; |\; TX_ \star X_a \; |\; X_( EX_) \; |\; a,\; \hfill \\
\left. {X_ + \to + ,\;X_ \star \to \star ,\;X_( \to (,\;X_) \to ),\;X_a \to a} \right\} \hfill \\
\end{gathered}[/m]
mit [m]V_2 : = V_1 + \left\{ {X_ + ,\;X_ \star ,\;X_( ,\;X_) ,\;X_a } \right\}[/m].
Danach verändern wir alle Produktionen, die auf der rechten Seite zu viele Variablen haben und erhalten:
[m]\begin{gathered}
P_4 = \left\{ {E \to E\alpha \; |\; T\beta _2 \; |\; T\gamma \; |\; X_( \beta _4 \; |\; a,\;} \right. \hfill \\
T \to T\beta _2 \; |\; T\gamma \; |\; X_( \beta _4 \; |\; a,\; \hfill \\
X_ + \to + ,\;X_ \star \to \star ,\;X_( \to (,\;X_) \to ),\;X_a \to a,\; \hfill \\
\beta _2 \to X_ \star \beta _3 ,\;\beta _3 \to X_( \beta _4 ,\;\beta _4 \to EX_) ,\; \hfill \\
\left. {\alpha \to X_ + T,\;\gamma \to X_ \star X_a) } \right\} \hfill \\
\end{gathered}[/m]
mit [m]V_3 : = V_2 + \left\{ {\alpha ,\;\beta _2 ,\;\beta _3 ,\;\beta _4 ,\;\gamma } \right\}[/m].
Wir erhalten also die Grammatik [m]G^{'} = \left({V_3 ,\;\Sigma ,\;P_4 ,\;S} \right)[/m], welche in CNF ist.
Nun würde ich gerne wissen, ob ich es richtig gemacht habe und auch keine Zwischenschritte vergessen habe. Und wie komme ich von dieser Form auf die Greibach NF?
Vielen Dank!
Grüße
Karl
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:24 So 09.01.2005 | | Autor: | Eva |
Hallo Karl!
![[sorry]](/images/smileys/sorry.gif "[sorry]") leider kann Dir hier niemand mit Deiner Frage weiterhelfen.
Da die Fälligkeit bereits abgelaufen ist, gehe ich davon aus, dass Du an einer Antwort nicht mehr interessiert bist!
Trotzdem liebe Grüße,
Eva
|
|
|
|
