endliche (reguläre) Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:54 So 08.12.2013 | | Autor: | tonno |
| Aufgabe | | Beweisen oder widerlegen Sie, dass es co-endliche Sprachen L gibt, sodass L* nicht regulär ist. |
Hier heißt eine Sprache L co-endlich gdw. [mm] \Sigma [/mm] * [mm] \backslash [/mm] L endlich.
Weiter ist bisher nur definiert: Eine Sprache heißt regulär, wenn sie durch einen regulären Ausdruck beschrieben werden kann. Und die Menge der regulären Sprachen ist abgeschlossen (bzgl. Vereinigung etc.).
Zunächst kann Ich damit relativ wenig anfangen. Wo nutze Ich die Endlichkeit von [mm] L^C [/mm] ?
Meine Überlegung: Ich versuche die Implikation [mm] "\forall [/mm] Sprache L: L co-endlich [mm] \Rightarrow [/mm] L* regulär" irgendwie zu beweisen oder zu widerlegen. Vorweg würde Ich behaupten, die Aussage ist wahr, aber Ich kann mir keinen Reim darauf machen, wie Ich es beweisen sollte.
Wenn Ich über Kontraposition gehe: Kann Ich zeigen, dass aus "L* nicht regulär" folgt, dass L nicht regulär und damit L nicht co-endlich? Oder geht es einfacher.
PS: [mm] \Sigma [/mm] ist das Alphabet, * der Kleene-Abschluss (-Hülle).
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:56 Di 10.12.2013 | | Autor: | Bennet |
Hi,
Wie du schon gesagt hast, gilt für reguläre Sprachen die Abgeschlossenheit bei der Bildung des Komplements.
Weiterhin ist jede Sprache die endlich ist, regulär.
Was gilt dann also für L, wenn [mm] \overline{L} [/mm] endlich und damit regulär ist. Und was muss dann auch für L* gelten?
Wenn du dir darüber Gedanken machst, ist der Beweis reine Formsache.
|
|
|
|
