0 Daumen
73 Aufrufe

Frage:

Ich muss entscheiden, ob folgende Aussage richtig ist:

"Gegeben sei die kontextfreie Grammatik G = ({S}, {a,b}, R,S) mit R = {S -> aSa | bSb}.

Dann ist L(G) regulär. "

Die Musterlösung besagt: "Wahr, denn: L(G) = ∅ und ∅ ist regulär. "


Aber wie komme ich denn mit den Regeln aus R bitteschön auf ∅ ???


Code:

von

1 Antwort

0 Daumen
 
Beste Antwort

Auf der rechten Seite jeder Regel steht ein Nichtterminalsymbol. Es können deshalb nur Wörter abgeleitet werden, die ein Nichtterminalsymbol enthalten. Die Wörter von L(G) enthalten kein Nichtterminalsymbol.

von 4,6 k

Nichtterminalsymbole, also Variablen sind ja die Großbuchstaben.

Man könnte z.B. aaSaa ableiten. Aber es gibt keine Regel S -> ε. Also wäre S doch immer mit in der Qonclusio. Egal, welches Wort man ableiten würde.

"Die Wörter von L(G) enthalten kein Nichtterminalsymbol."

Ist das laut Definition so, oder wie kommst du darauf? Ist das bei regulären Sprachen bzw. Grammatiken immer so?

Das ist laut Definition für jede Grammatik \(G\) so, weil die Menge der Nitchtterminalsymbole \(\Gamma\) disjunkt zu der Menge der Terminalsymbole \(\Sigma\) ist und \(L(G)\subseteq \Sigma^*\) ist.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community