Beiträge von Stefan_Sch

  • Reguläre Sprache

    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

    Code
    S -> Sab
S -> ab

    also durch

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

    Hier mal der Ableitungsbaum:

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

  • Reguläre Sprache

    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? :)

  • Reguläre Sprache

    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:

  • 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?

    Code
    S -> Sab
S -> ab

    :confused:

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

    Code
    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.