Abschlusseigenschaften < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:24 Di 11.11.2008 | | Autor: | RalU |
| Aufgabe | Hallo,
Formen Sie die Sprachen L1 und L2 mit Hilfe der Abschlusseigenschaften regulärer Sprachen jeweils in die Sprache L01 um. Warum folgt dass, weder L1 noch L2 regulär sind?
1. L1= { [mm] 0^{i}1^{j}|i!=j [/mm] }
2. L2= { [mm] 0^{k}1^{m}2^{k-m}|k>=m>=0 [/mm] } |
Also Abschlusseigenschaften sind laut meiner VL ja
Vereinigung, Durschschnitt, Komplement und Mengendifferenz,
Konkatenation und Iteration, Spiegelung, Homomorphismen und inverse Homomorphismen.
Also wenn ich 1. und 2. in die Sprache L01 gewandelt kriege, weiß ich, dass 1. und 2. nicht regulär sein können, weil auch L01 nich regulär ist.
Mein Problem ist aber, wenn ich jetzt nur mal die 1. betrachte:
die Sprache L01 ist definiert als L1= { [mm] 0^{k}1^{k}|k [/mm] aus [mm] \IN [/mm] }
Wie kann ich denn diese "Gleichheit" der Exponenten mit der Definition für 1. (vgl. i!=j)vereinbaren?
Eine Überlegung wäre, dass L1 [mm] \subseteq [/mm] L01 ist...
Aber wie wandelt man sowas um?
Gruß, Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:37 Do 13.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
