Diskussion:Linkslineare Sprachen - reguläre Sprachen

Allerdings haben wir von einer linkslinearen Sprache nur verlangt, dass es eine linkslineare Grammatik zu ihr gibt. Die Sprache zum Beispiel 4 aus Allgemeine Regelsprachen ist eine linkslineare Sprache, denn sie wird auch von folgender linkslinearen Grammatik erzeugt:

Sicher, dass Beispiel 4 aus Allgemeine Regelsprachen eine linkslineare Sprache ist? Diese verwendet doch diese Regel:

     P = {(S -> aTU),
        (bU -> a),
        (U -> ST | ab),
        (Tb -> SUb),
        (Ta  -> SaT)} <-- ein terminales Zeichen wird von zwei Nichtterminalen eingeschlossen

Widerspricht das nicht der Definition der linkslinearen Sprachen?

---

--Stas 11:54, 27. Okt 2006 (CEST)

Denke nicht das das der Definition widerspricht. Zur Sprache gibt es eine linkslineare Grammatik, somit ist die Sprache linkslinear. Das es auch nicht linkslineare Grammatiken gibt, die diese Sprache erzeugen, ändert jedoch nichts an dieser Tatsache. Die Sprache bleibt linkslinear.

Eine andere Frage hätte ich aber auch noch:

    Ist L linkslinear, so auch das Komplement $V_T^* \setminus L$. 
        Der Beweis ist nicht so einfach wie die vorhergehenden. Wir übergehen ihn deshalb.

Könnte man dies nicht wie folgt begründen: Ein Terminal ist immer linkslinear. Eine Konkatenation von linkslinearen Worten ist ebenfalls linkslinear. Unabhängig davon ob eine Reihung von linkslinearen Worten bereits in der Sprache selbst erfasst ist oder nicht, muss diese immer linkslinear sein. --steve 19:20, 27. Okt 2006 (CEST)

@Stas: Nein, dies widerspricht nicht der Definition. Das von dir hier angegebene Beispiel 4 ist keine linkslineare Grammatik. Dies beduetet aber nicht, dass die Sprache nicht linkslinear sein kann. Denn sollte es eine Grammatik geben (z.B. die angegebene mit P= {(S->S)}), welche die gleiche Sprache beschreibt und die linkslinear ist, gilt dies auch für die Sprache (engere Definition). Letztlich sind die Sprachen so aufgebaut, dass allgemeinere Sprache die spezielleren enthalten, d.h. z.B. ist jede reguläre Sprache auch eine kontextfreie - aber nicht umgekehrt.--Ingo Höpping 14:51, 28. Okt 2006 (CEST)

@Steve: Hm, da bin ich überfragt. Hab auch - auf die Schnelle - keinen Beweis gefunden. Wäre bestimmt interessant, mal ein Beispiel zu konstruieren und dann Sonderfälle zu betrachten. Ich glaube aber nicht, dass es so einfach wäre.--Ingo Höpping 15:10, 28. Okt 2006 (CEST)