Rechtslineare Grammatiken < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben sie für die die Sprache L = {w [mm] \in [/mm] {a,b}* | w enthält nicht das Teilwort abb} eine rechtslineare Grammatik an. |
Wir haben zu diesen Aufgaben Musterlösungen, allerdings sieht meine Lösung etwas anders aus. Die Musterlösung scheint meiner Meinung nach richtig zu sein, deswegen die Frage: Kann es für Sprachen 2 verschiedene rechtslineare Grammatiken geben?
Falls nein, würde ich hier gerne mal meine Lösung angeben. Kann mir jemand bestätigen, ob sie richtig oder falsch ist?:
G = ( {x,y} , {a,b} ,X, { [mm] X->aX|bY|\varepsilon,Y->aY,|abY|\varepsilon [/mm] } )
Musterlösung ist:
G = ( {x,y} , {a,b} ,X, { [mm] X->bX|aY|\varepsilon,Y->aY|baY|b|\varepsilon [/mm] } ).
Gruß und Danke
GHoernle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:45 Do 26.08.2010 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Moin,
> Geben sie für die die Sprache L = {w [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{a,b}* | w
> enthält nicht das Teilwort abb} eine rechtslineare
> Grammatik an.
> Wir haben zu diesen Aufgaben Musterlösungen, allerdings
> sieht meine Lösung etwas anders aus. Die Musterlösung
> scheint meiner Meinung nach richtig zu sein, deswegen die
> Frage: Kann es für Sprachen 2 verschiedene rechtslineare
> Grammatiken geben?
>
> Falls nein, würde ich hier gerne mal meine Lösung
> angeben. Kann mir jemand bestätigen, ob sie richtig oder
> falsch ist?:
>
> G = ( {x,y} , {a,b} ,X, {
> [mm]X->aX|bY|\varepsilon,Y->aY,|abY|\varepsilon[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} )
Deine Loesung ist falsch: damit kannst du z.B. nicht das Wort bb erzeugen, was sehr wohl in der Sprache $L$ liegt.
Du wuerdest $X \to bY$ machen und dann hast du keine Regel, aus $Y$ etwas zu machen was mit $b$ anfaengt.
> Musterlösung ist:
>
> G = ( {x,y} , {a,b} ,X, {
> [mm]X->bX|aY|\varepsilon,Y->aY|baY|b|\varepsilon[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
} ).
Hier bekommst du das Wort etwa ueber $X \to bX \to bbX \to bb$.
LG Felix
|
|
|
|
