Hi!

Sitze grad an Aufgabe 2.2.
Was eine kontextfreie Grammatik ist, ist klar, eine reguläre auch (steht ja im Text der Aufgabe). Aber was habe ich unter einer rechtsseitig linearen kontextfreien Grammatik zu verstehen?
Rechtsseitig ist klar, rechte Seite der Abbildung P, kontextfrei an sich auch klar. aber linear kontextfrei??? Soll das heißen, das P linear ist? (Ist es das nicht immer?!)

HILFE HILFE HILFE

Kapitel 1 , Folie 30 (Seite 15).
Es muss für P gelten:
[latex]$\subseteq$ N $\times$ $\left ( \Sigma^* \cup \Sigma^* \bullet N \right )$ [/latex]
Dann ist P rechtslinear.
Meiner Meinung nach bedeutet rechtsseitig linear nichts anderes als das P rechtslinear, aber nicht linkslinear ist(links linear und rechts linear wäre es nur in demm Fall wenn du Regeln hättest die rechtsseitig nur Nonterminale besitzen).

Rechtsseitig linear könnte auch bedeuten, dass die Grammatik auf der "rechten Seite der Regeln" linear ist, also rechtslinear oder linkslinear.

Mit "rechtsseitig linear" und "linksseitig linear" ist rechtslinear bzw. linkslinear
gemeint. Diese Begriffe sind auf Folie 30 definiert.

Wird zwar für die Aufgabe nicht benötigt, aber da du danach fragst:
Eine kontextfreie Grammatik G=(\Sigma,N,P,S) heißt linear, falls
[latex]P\subseteq N\times (\Sigma^*N\Sigma^* \cup \Sigma^*)[/latex].
Mit anderen Worten: falls auf jeder rechten Seite höchstens ein Nonterminal
vorkommt.

Dankeschön!