Wann ist eine Grammatik kontextfrei? |
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
Wann ist eine Grammatik kontextfrei? |
|
Hallo,
ich habe letztens eine einfache Frage gesehen die ich nicht kurz und knapp beantworten konnte.
Wann ist eine Grammatik kontextfrei?
Kann die Frage kurz und knapp beantwortet werden? Wäre super.
Danke und Grüße
Daniel
__________________ ---
Gegenseitiges helfen verbindet
|
|
13.10.2007 14:48 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Eine Grammatik ist kontextfrei, wenn es nur Produktionsregeln der Form gibt mit Nichtterminalsymbol und Satzform .
Also kurz: Durch Produktionsregeln darf immer nur ein Nichtterminalsymbol auf eine Satzform abgeleitet werden.
|
|
13.10.2007 15:18 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
wäre die einfachste Möglichkeit.
|
|
13.10.2007 17:34 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
ja aber wenn ich nur a erzeugen will dann würde es ja wie oben nicht gehen.
Dann
S->aA
A->bc|epsilon ????
Würde es so gehen?
__________________ ---
Gegenseitiges helfen verbindet
|
|
13.10.2007 17:45 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ich glaube du musst erstmal sagen, welche reguläre Sprache du als Grammatik ausdrücken willst.
|
|
13.10.2007 19:16 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ja, dann stimmt deine Grammatik. Ist ja auch leicht zu überprüfen, da du A nur zu bc oder Epsilon ableiten kannst.
|
|
13.10.2007 19:30 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
mir geht es mehr um die form.
Wollte den Unterschied von regulären und kontextfreien Produktionen verstehen.
Da es ja eine reguläre Grammatik sein sollte müsste dann die Produktion wie folgt nicht erlaubt sein: 1. S-> aAB
2. S->aAc ?
Fragen:
A: Ist die reguläre Grammatik wie bei 1 richtig? also mehrere Nichtterminale nach a ?
B: Die 2. Grammatik müsste allerdings eine CfG sein oder?
Danke und Grüße
Daniel
__________________ ---
Gegenseitiges helfen verbindet
|
|
13.10.2007 19:55 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Das kann man so allgemein nicht behaupten, denn
S-> aAB
A -> a
B -> b
erzeugt eine reguläre Sprache.
|
|
13.10.2007 21:14 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
Ja dann sehe ich denn Unterschied zu einer CfG darin, dass man in der Lage ist folgendes zu machen: S-aABc also noch die Option noch ein Nichtterminal einzufügen.
__________________ ---
Gegenseitiges helfen verbindet
|
|
13.10.2007 21:23 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Nein, das hat garnichts damit zu tun. Denn du kannst soviele Nichtterminale wie du willst haben, wenn diese z.B. nur auf ein einfaches Terminalsymbol abgeleitet werden.
|
|
13.10.2007 21:31 |
|
|
Daniel07
Jungspund
Dabei seit: 18.09.2007
Beiträge: 13
Herkunft: DE
|
|
Das wäre sehr nett. Ich denke, dass ich es dann besser verstehen würde.
VLG
Daniel
__________________ ---
Gegenseitiges helfen verbindet
|
|
14.10.2007 13:27 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Und da findest du selber keine Beispiele?
Nimm z.B. die Palindrome
|
|
14.10.2007 14:18 |
|
|
|