kontextfreie Grammatik G, ist L(G) regulär?

Question

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:

Answer 1

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.

Comments

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.