Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Vereinigung nicht regulärer Sprachen
Autor
Universität/Hochschule J Vereinigung nicht regulärer Sprachen
LernenWollen
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.06.2019
Mitteilungen: 79
  Themenstart: 2020-02-02

Hi! An sich dürfte das jetzt keine große Sache sein, aber ich komme einfach nicht drauf. Gegeben $L_1, L_2$ nicht regulär. Ist $L_1 \cup L_2$ nicht regulär? Ich persönlich glaube schon, aber mir fehlt das Argument. Wenn ich Regularität annehme, finde ich keinen Weg zum Widerspruch und für die Alternative fällt mir kein Gegenbeispiel ein. Danke für Hinweise, Grüße LernenWollen


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.1, eingetragen 2020-02-02

Wähle eine nichtreguläre Sprache, deren Komplementär ebenfalls nicht regulär ist. Die Vereinigung ist offenbar regulär.


   Profil
LernenWollen
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.06.2019
Mitteilungen: 79
  Beitrag No.2, vom Themenstarter, eingetragen 2020-02-02

Eine nicht reguläre Sprache zu finden ist einfach. $\{a^nb^nc^m~|~n,m \in \mathbb{N}\}$ ist nicht regulär und $\{a^nb^nc^n~|~n \in \mathbb{N}\}$ ist ja nicht einmal kontextfrei. Was ist aber mit den Komplementen? Wie finde ich für die beiden Sprachen heraus, ob sie regulär sind oder nicht? Ich kann sie nicht einmal hilfreich aufschreiben: $\{w \in \{a, b, c\}~|~w \neq a^nb^nc^m \text{ mit } n, m \in \mathbb{N}\}$, $\{w \in \{a, b, c\}~|~w \neq a^nb^nc^n \text{ mit } n \in \mathbb{N}\}$.


   Profil
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3344
Wohnort: Berlin
  Beitrag No.3, eingetragen 2020-02-02

Das Komplement einer regulären Sprache ist wieder regulär.


   Profil
LernenWollen
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.06.2019
Mitteilungen: 79
  Beitrag No.4, vom Themenstarter, eingetragen 2020-02-04

\quoteon(2020-02-02 19:55 - ligning in Beitrag No. 3) Das Komplement einer regulären Sprache ist wieder regulär. \quoteoff Das ist klar, aber es hilft mir nicht. $\{a^nb^nc^m~|~n,m \in \mathbb{N}\}$ ist nicht regulär und $\{a^nb^nc^n~|~n \in \mathbb{N}\}$ ist auch nicht regulär. Wie weiß ich bei nicht regulären Sprachen wie bei diesen, ob das Komplement regulär ist? \quoteon(2020-02-02 17:38 - DerEinfaeltige in Beitrag No. 1) Wähle eine nichtreguläre Sprache, deren Komplementär ebenfalls nicht regulär ist. \quoteoff Ich kenne keine nicht reguläre Sprache, deren Komplement nicht regulär ist, weil ich keinen Weg finde, wie ich bei einer nicht regulären Sprache ausschließe, dass das Komplement regulär ist. \quoteon(2020-02-02 17:38 - DerEinfaeltige in Beitrag No. 1) Die Vereinigung ist offenbar regulär. \quoteoff Das möchte ich nachprüfen. Leider zweifel ich die Aussage an, da $L \cup \overline{L} = \Sigma^*$ ist und das nie regulär ist - so jedenfalls mein Verständnis. !!! Nachtrag: Quark, ein Automat mit einem Zustand erkennt $\Sigma^*$ ... ich glaube, ich verstehe, damit scheint die Grundfrage geklärt, aber noch nicht die, wie ich bei den beiden nicht regulären Sprachen das Komplement auf Regularität prüfe. !!! LG LernenWollen


   Profil
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3344
Wohnort: Berlin
  Beitrag No.5, eingetragen 2020-02-05

\quoteon(2020-02-04 23:49 - LernenWollen in Beitrag No. 4) \quoteon(2020-02-02 19:55 - ligning in Beitrag No. 3) Das Komplement einer regulären Sprache ist wieder regulär. \quoteoff Das ist klar, aber es hilft mir nicht. \quoteoff Sollte es aber ... \quoteon weil ich keinen Weg finde, wie ich bei einer nicht regulären Sprache ausschließe, dass das Komplement regulär ist. \quoteoff ... denn wenn das Komplement regulär wäre, wäre das Komplement vom Komplement, also die ursprüngliche Sprache, ja bereits regulär!


   Profil
LernenWollen
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.06.2019
Mitteilungen: 79
  Beitrag No.6, vom Themenstarter, eingetragen 2020-02-05

"Den Wald vor lauter Bäumen nicht sehen können." Natürlich. Was ist das ärgerlich, wenn man das Einfache nicht sieht. Ich bedanke mich herzlich und schließe dieses Thema, da alle Fragen vollumfänglich beantwortet sind. LG LernenWollen


   Profil
LernenWollen hat die Antworten auf ihre/seine Frage gesehen.
LernenWollen hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]