Wann ist eine Grammatik kontextfrei?

13.10.2007, 14:48	Auf diesen Beitrag antworten »
Daniel07	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


13.10.2007, 15:18	Auf diesen Beitrag antworten »
Tobias	Eine Grammatik $[latex](N, \Sigma, P, S)[/latex]$ ist kontextfrei, wenn es nur Produktionsregeln der Form $[latex]A \to \alpha[/latex]$ gibt mit Nichtterminalsymbol $[latex]A \in N[/latex]$ und Satzform $[latex]\alpha \in (N \cup \Sigma)^\ast[/latex]$ . Also kurz: Durch Produktionsregeln darf immer nur ein Nichtterminalsymbol auf eine Satzform abgeleitet werden.
13.10.2007, 16:40	Auf diesen Beitrag antworten »
Daniel07	also nur die Möglichkeit und Art der Produktionsregeln? Bei einer CfG können Produktionen der Art: S-> aBCa \|aBC\|Abc\|AbC und bei regulären Sprachen können nur Produktionen der Art: S-> aA\|epsilon oder S->Aa\|epsilon. Wie werden enstehen wörter bei regulären Grammatiken? Kannst du mir vielleicht ein kleines Beispiel geben? Wie lautet die Grammatik zu abc? So zB.:? S->aB B->bc \|epsilon ?? Vielen Dank und Grüße Daniel
13.10.2007, 17:34	Auf diesen Beitrag antworten »
Tobias	$[latex]S \to abc[/latex]$ wäre die einfachste Möglichkeit.
Anzeige

13.10.2007, 17:45	Auf diesen Beitrag antworten »
Daniel07	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?
13.10.2007, 19:16	Auf diesen Beitrag antworten »
Tobias	Ich glaube du musst erstmal sagen, welche reguläre Sprache du als Grammatik ausdrücken willst.
13.10.2007, 19:25	Auf diesen Beitrag antworten »
Daniel07	Also ich habe das letzte auf eine reguläre Sprache/Grammatik bezogen. abc ist eine Wort das von einer regulären Grammatik erzeugt werden soll. Alternativ hatte ich gedacht soll auch nur a\| abc erzeugt werden können. Also sowohl "a" als auch "abc" soll meine reguläre Grammatik erzeugen. Gruß Daniel
13.10.2007, 19:30	Auf diesen Beitrag antworten »
Tobias	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:55	Auf diesen Beitrag antworten »
Daniel07	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
13.10.2007, 21:14	Auf diesen Beitrag antworten »
Tobias	Das kann man so allgemein nicht behaupten, denn S-> aAB A -> a B -> b erzeugt eine reguläre Sprache.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »