Schnittmenge und Vereinigung einer regulären und einer nicht regulären Sprache

12

Sei regulär, regulär, nicht regulär. Zeigen Sie, dass nicht regelmäßig ist, oder geben Sie ein Gegenbeispiel an.L1L1L2L2L1L2

Ich habe versucht: Schauen Sie sich . Dieser ist regelmäßig. Ich kann dafür einen endlichen Automaten konstruieren: ist regulär, ist regulär, also entferne alle Pfade (endliche Menge) für aus der endlichen Menge von Pfaden für . Es gibt also eine begrenzte Anzahl von Wegen für diese ganze Sache. Dieses Ding ist nicht mit , aber wie kann ich beweisen, dass die Vereinigung von (regulär) und (nicht regulär) nicht regulär ist?L1(L2L1)L1L2L1L1L2L1L2L1(L1L2)L2

Kevin
quelle
" entferne alle Pfade (endliche Menge) für aus der endlichen Menge der Pfade für " - was soll das heißen? Der übliche Weg, einen Automaten für die Differenz zu konstruieren, besteht darin, und die bekannten Konstruktionen für Komplement und Schnittmenge zu verwenden. L 1 A B = A ¯ BL1L2L1AB=AB¯
Raphael
Ich bevorzuge es, den Titel dieser Frage zu ändern. An sich ist der Fragentitel eine falsche Aussage.
Nitishch

Antworten:

19

Das können wir durch Widerspruch beweisen. Definieren wir . Dann können wir neu :L1¯=ΣL1L2

L2=((L1L2)L1)(L1L2)=((L1L2)L1¯)(L1L2)

Wir wissen:

  • Reguläre Sprachen sind unter Vereinigung, Überschneidung und Ergänzung geschlossen
  • L1L2L1¯ und sind regulärL1L2
  • L2 ist nicht regelmäßig

wir nun an, ist regulär: Dann ist regulär (da es sich nur um eine Vereinigung / Schnittmenge regulärer Sprachen handelt) wäre . Das ist ein Widerspruch, daher ist unsere Annahme falsch und kann nicht regelmäßig sein. ( ( L 1L 2 ) ¯ L 1 ) ( L 1L 2 ) L 2 L 1L 2L1L2((L1L2)L1¯)(L1L2)L2L1L2

Mike B.
quelle
Ich denke ich habe es. Aber warum ist die Ergänzung einer regulären Sprache regelmäßig? Ich verstehe diesen Teil nicht.
Kevin
1
@ Kevin Dies ist ein bekanntes Lemma, daher sollten Sie in jedem Lehrbuch einen Beweis finden. Eine Beweismethode besteht darin, einen endlichen Automaten zu nehmen und die akzeptierenden und nicht akzeptierenden Zustände zu tauschen: Sie erhalten einen Automaten, der die Komplementsprache erkennt.
Gilles 'SO- hör auf böse zu sein'
Und was ist mit nicht deterministischen endlichen Automaten? Angenommen, wir haben Automaten. , ein Anfangszustand, zwei Pfeile von diesem Zustand mit in einen anderen Zustand. Einer dieser Staaten akzeptiert und einer nicht. Also ist . Wenn wir jetzt die akzeptierenden Zustände tauschen, akzeptiert es immer noch , so dass es nicht gilt, dass es die Komplementsprache akzeptiert! a L ( M ) = { a } { a }A={a,b}aL(M)={a}{a}
Kevin
Gilles 'Beweis funktioniert nur für deterministische endliche Automaten, was - für reguläre Sprachen - keine Einschränkung darstellt. Aber wie er sagte, kann dieses Lemma in jedem Lehrbuch gefunden werden.
Mike B.
1
@ Kevin: Mike bedeutet, dass jede reguläre Sprache einen deterministischen Automaten hat, der sie erkennt, so dass Sie immer einen benutzen können.
reinierpost
-4

Das ist falsch. Betrachte , . ist , nicht; aber .L1={a,b}L2={anbn:n0}L1L2L1L2=L1

vonbrand
quelle
5
Sie haben die Bedingung, dass L1L2 regulär ist, nicht erfüllt .
Andrej Bauer