Grammatik umschreiben < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Schreiben Sie die linkslineare Grammatik [mm]G=\{ \Phi=\{S\},\Sigma=\{a,b,l\},\{S::=Sbla|\epsilon\},S \}[/mm] in eine äquivalente Grammatik mit Regeln der Form [mm]A::=Bx[/mm] oder [mm]A::=x[/mm] um, wobei [mm]A,B \in \Phi', x \in (\Sigma \cup \{\epsilon\})[/mm]. (x ist leer oder ein einziges Zeichen.)
Ist die neue Grammatik ebenfalls linkslinear? |
Hallo zusammmen,
ich finde bei dieser Aufgabe leider keinen Ansatz.
Offensichtlich ist [mm]\Phi' = \{S,A,B\}[/mm]. Wenn ich die Aufgabe richtig verstehe, ist [mm]x=\epsilon|a|b|l[/mm].
Wie aber kann ich sicherstellen, dass für x nur ein ganz bestimmtes Zeichen eingesetzt wird? Immerhin muss die Grammatik ja die Sprache der Wörter bla, blabla, blablabla usw. erzeugen. Es kommt also auf die Reihenfolge der b, l und a an. Hier könnte A aber durch Ba, Bb, Bl oder B ersetzt werden.
Habt Ihr einen Tipp für mich?
Viele Grüße
|
|
| |
|
Die "neue" Grammatik muss doch nur von der Form sein!
Wie du letztlich die Hilfssymbole nennst ist egal. Mach doch einfach für jeden Buchstaben einen eigene Regel, so dass nur l auf a folgen kann usw...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:09 So 03.11.2013 | | Autor: | casiokid |
A:= Ba wäre z.B. eine Regel von der Form A:=Bx.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:27 So 03.11.2013 | | Autor: | Apfelchips |
> Die "neue" Grammatik muss doch nur von der Form sein!
Oh je, Du hast natürlich recht. Danke!
|
|
|
|
