Chomsky-Normalform < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:12 Di 07.05.2013 | | Autor: | bandchef |
| Aufgabe | | Wandeln Sie die kontextfreie Grammatik [mm] $G=(V,\Sigma,P,S)$ [/mm] mit [mm] $V=\{S,A,B\}$, $\Sigma=\{a,b\} [/mm] und [mm] $P=\{S \to ASA | aB, A \to B|S, B \to b|\epsilon\}$ [/mm] in Chomsky-Normalform um. |
Hi Leute!
Ich weiß, dass ich diese Aufgabe schon vor kurzer Zeit gestellt habe, aber leider habe ich ja darauf keine Antwort bekommen und da die Fälligkeit abgelaufen ist, konnte ich keine weitere "Fragen", in diesem Fall ja eigentlich "Antwort", darauf stellen...
Hier nun ein neuer Versuch. Vor allem denke ich auch, dass ich hier nun einige Fehler ausgemerzt habe. Ich hoffe, jemand kann mir nun sagen, ob das so richtig ist:
Eliminierung [mm] $\epsilon$-Regel [/mm] (1. Runde):
[mm] $P=\{S \to ASA, S \to aB, S \to a, A \to B, A \to \epsilon, A \to S, B \to b\}$
[/mm]
Eliminierung [mm] $\epsilon$-Regel [/mm] (2. Runde):
[mm] $P=\{S \to ASA, S \to SA, S \to AS, S \to S, S \to aB, S \to a, A \to B, A \to S, B \to b\}$
[/mm]
Eliminierung Kettenregel:
[mm] $P=\{S \to ASA, S \to SA, S \to AS, S \to aB, S \to a, A \to b, A \to ASA, A \to SA, A \to AS, A \to aB, A \to a, B \to b\}
[/mm]
Separation von Terminal und Nicht-Terminal:
[mm] $P=\{S \to ASA, S \to SA, S \to AS, S \to V_aB, S \to a, A \to b, A \to ASA, A \to SA, A \to AS, A \to V_aB, A \to a, B \to b, V_a \to a\}$
[/mm]
Eliminierung von Nicht-Terminal-Ketten:
[mm] $P=\{S \to AS_1, S_1 \to SA, S \to SA, S \to AS, S \to V_aB, S \to a, A \to b, A \to AS_2, S_2 \to SA, A \to SA, A \to AS, A \to V_aB, A \to a, B \to b, V_a \to a\}$
[/mm]
So, ich hoffe jetzt passt das soweit alles. Ich würde mich sehr freuen, wenn da jemand kurz drüberlesen könnte und mir Rückmeldung gibt!
|
|
| |
|
Hallo bandchef,
> [mm]P=\{S \to AS_1, S_1 \to SA, S \to SA, S \to AS, S \to V_aB, S \to a, A \to b, A \to AS_2, S_2 \to SA, A \to SA, A \to AS, A \to V_aB, A \to a, B \to b, V_a \to a\}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]") passt! 
BTW warum schreibst Du eigentlich jede Ableitung einzeln anstatt mit | ? Ich persönlich finde das viel übersichtlicher.
> So, ich hoffe jetzt passt das soweit alles. Ich würde mich
> sehr freuen, wenn da jemand kurz drüberlesen könnte und
> mir Rückmeldung gibt!
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:37 Mi 08.05.2013 | | Autor: | bandchef |
Danke! Du hast mir sehr geholfen! Jetzt weiß ich, dass ich die ganzen Ersetzungsregeln richtig anwende!
|
|
|
|
