CNF < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei die Grammatik G = ({0},{A,B},R,A) mit
R:
- A -> BAB | B | [mm] \varepsilon
[/mm]
- B -> 00 | [mm] \varepsilon
[/mm]
Überführen Sie G in die Chomsky-Normalform. |
Erstmal schönen, guten Tag.
Ich habe ein paar Probleme mit den [mm] \varepsilon-Produktionen.
[/mm]
Ich sollte doch jetzt als Ersten Schritt versuche diese zu eliminieren, oder!? Aber dann doch nur bei B, da A der Startzustand ist und ich daher das da nich machen brauch/muss/darf?
Ich habe mir da eine Lösung zusammen gemogelt, bin mir aber ziemlich sicher das diese nicht stimmt. Wäre Klasse wenn jemand drüber gucken könnte!
1.
A -> BAB | B | [mm] \varepsilon
[/mm]
B -> 00 | A
2.
A -> BC | B | [mm] \varepsilon
[/mm]
B -> DD | A
C -> AB
D -> 0
Ist das so korrekt? Bzw. was ist falsch?
Schonmal Danke!
Mit freundlichen Grüßen
DerdersichSichnennt
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 01:45 Mi 12.08.2009 | | Autor: | cycore |
hallo
also das ist bei mir jetzt auch schon ein bisschen her, also so 100% sicher bin ich mir nicht, aber wobei ich mir sicher bin ist, dass du das [mm] \epsilon [/mm] nicht ohne weiteres aus B streichen darfst - das hat noch auswirkungen auf A!
und richtig, die startproduktion darf das [mm] \epsilon [/mm] behalten.
also so wie ich das in Erinnerung hab gilt beim streichen des [mm] \epsilon, [/mm] dass dann (in deinem Fall) in der Produktion A das BAB durch BA | AB ersetzt werden muss und dann bist du fertig, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:50 Mi 12.08.2009 | | Autor: | Andrey |
> 1.
>
> A -> BAB | B | [mm]\varepsilon[/mm]
> B -> 00 | A
Woher kommt plötzlich "B->A"?
Um epsilon-Produktionen zu eliminieren, fügt man ein zusätzliches startsymbol hinzu, das nach epsilon abgeleitet werden darf.
Alle Produktionen mit epsilon-ableitbaren Nichtterminalen müssen solange aufgespalten werden, bis man alle kombinationen hat, die möglich wären, wenn man die epsilon-Ableitbaren wegschmeißen dürfte.
Zum beispiel:
A,B sind beide zu epsilon ableitbar.
A->BAB
wird daher ersetzt durch
A->BAB |AB | BB | BA | B | A
anschließend werden die epsilons überall außer beim neuen startsymbol weggemacht.
Das ergebnis sollte so aussehen:
Grammar = (
Terminals = {0},
Nonterminals = {$,<0>,<AB>,A,B},
StartSymbol = $,
Productions =
{
$ -> eps | AB | BB | BA | B<AB> | <0><0>
<0> -> 0
<AB> -> AB
A -> AB | BB | BA | B<AB> | <0><0>
B -> <0><0>
}
)
hab's selbst nicht im detail nachgerechnet, sieht aber korrekt aus, die Rechner irren sich da selten.
greetz, Andrey.
|
|
|
|
