Reguläre Sprache

Hi,

ich habe ein kleines Verständnisproblem mit regulären Sprachen. Warum erzeugt das folgende Beispiel eine reguläre Sprache und keine kontextfreie?

S -> Sab
S -> ab

:confused:

Auch bei dem folgenden Beispiel hätte ich auf eine kontextfreie Sprache getippt, sie ist aber auch regulär.

S -> aA
A -> aAA
A -> a

Ich dachte bei Typ 3 Sprachen gilt folgender Leitsatz:

Zitat

Auf der linken Seite jeder Regel der Grammatik steht genau ein nicht-terminales Symbol. Auf der rechten Seite steht bei den sogenannten rechtsregulären Grammatiken genau ein Terminal, optional gefolgt von einem Nicht-Terminal. Bei den sogenannten linksregulären Grammatiken steht auf der rechten Seite jeder Regel ein Terminal, dem optional ein Nicht-Terminal vorangeht.

Oben im ersten Beispiel ist aber ein Nicht-Terminal gefolgt von zwei Terminalen.

Im zweiten Beispiel ein Terminal gefolgt von zwei Nicht-Terminalen.

:confused:

Das erste Beispiel könnte nach eigener Überlegung natürlich durchaus linkslinear sein, das zweite rechtslinear. Dummerweise bringt das die obige Definition durcheinander.

Hallo,

danke für diese interessante Antwort! :o

Das wirft ein paar Fragen auf. Kann eine reguläre Sprache prinzipiell von allen Grammatiken erzeugt werden?

Ich dachte eine kontextfreie Grammatik erzeugt automatisch eine kontextfreie Sprache?

:confused:

Zitat von mdk

Tut sie auch. Nur sind die regulären Sprachen eine Teilmenge der kontextfreien.

Ok. Prinzipiell bedeutet das dann, dass ich selbst mit einer kontextsensitiven Grammatik eine reguläre Sprache erzeugen kann. Umgekehrt kann ich aber keine Typ 1 Sprache mit einer links- oder rechtslinearen Grammatik erzeugen?

Ist das korrekt?

Zitat von mdk

Ja.

Sehr schön!

Eine letzte Frage noch.

Dann müsste das erste Beispiel durch die von mir kurz gefasste folgende linkslineare Grammatik ersetzt werden können, oder? :o

S -> Sab
S -> ab

also durch

S -> Ab
A -> Ba
B -> Ab
A -> a

Hier mal der Ableitungsbaum:

S
         | \
         A  b
       / |  |
      B  a  b
    / |  |  |
   A  b  a  b
   |  |  |  |
   a  b  a  b

Zitat von mdk

Ja, sollte so stimmen.

Danke! Du hast mir geholfen ein paar Unklarheiten zu beseitigen.

Viele Grüße,
Stefan