Sprache auf Regularität überprüfen
-
Hi Leute!
Hab da eine Aufgabe mit der ich nicht weiterkomme.
Beweisen oder widerlegen sie, dass die folgende Sprache regulär ist:
L={0^n 1^n | n != m}
Das Pumping-Lemma darf nicht verwendet werden.
Könnt ihr mir helfen? Hab da schon wieder überhaupt keine Ahnung wie das gehen soll, insbesondere ist hier jetzt auch noch das PL verboten...
-
Um zu beweisen, dass sie regulär ist, könntest du versuchen, einen entsprechenden DFA oder NFA zu konstruieren. Dir wird auffallen, dass das nicht klappt, überlegen warum es nicht klappt und den Grund dann ausformuliert auf's Papier bringen.
-
Es gibt auch noch die Möglichkeit sich auf eine ähnliche Sprache zu beziehen, von der man weiß das sie regulär ist, oder nicht. Das ist gerade in Uniaufgaben und ähnliches sehr beliebt, da der Umfang der behandelten Sprachen überschaubar ist.
-
Ich vermute mal, da ist ein n falsch in der Aufgabenstellung. sonst macht m!=n keinen Sinn.
Mein Gedankenansatz:
L1={0^n 1^m } ist offensichtlich regulär.
L2={0^n 1^n} ist das offensichtlich nicht.Also ist L1 vereinigt L2 nicht regulär => L ist nicht regulär.
//edit ne ist falsch. Ich lass meine Dummheit aber trotzdem mal stehen.
Argumentiere einfach mit der Anzahl der Zustände des Automaten. Der Automat muss ja unterscheiden können, wann n!=m ist. Da aber die Anzahl der Zustände endlich ist, muss es ein n geben > der Anzahl der unterscheidbaren Zustände. Dmait muss der Automat in eine Shcleife gehen und damit einen Fehler machen
=> Sprache nicht regulär
-
@otze: das ist aber nichts anderes als das Pumping-Lemma, nur sozusagen "expandiert"
Mein Tipp: Wenn L regulär ist, dann ist auch das Komplement L^c regulär und dann ist auch L^c geschnitten 0*1* regulär... und das ist was?