Entscheidbar und Nich-Erkennbar und Union

Aufrufe: 139     Aktiv: vor 3 Monaten, 3 Wochen

0

Hallo zusammen

Folgendes verstehe ich nicht, warum soll zwei stimmen und drei nicht?

 

Vielen Dank für eure Hilfe!

 

Schöne Grüsse

Sayuri

gefragt vor 4 Monaten
s
sayuri,
Student, Punkte: 108

 
Kommentar schreiben Diese Frage melden
1 Antwort
1

Zu 3. Sei A nicht regulär (irgendeine nicht reguläre Sprache über \(\Sigma\)). Dann ist auch das Komplement A^c nicht regulär (denn wäre es regulär, wäre auch A^c^c=A regulär, Widerspruch). Mit B=A^c ist die Vereinigung von A und B aber \(\Sigma^*\), was regulär ist.

Kurz: Die Vereinigung von nicht regulären Sprachen kann regulär sein.

Zu 2. Was genau heißt hier "A entscheidbar"? Es sind doch nur Eigenschaften entscheidbar.

geantwortet vor 3 Monaten, 4 Wochen
m
mikn
Lehrer/Professor, Punkte: 8.31K
 

Achso jetzt verstehe ich es, vielen herzlichen Dank!   ─   sayuri, vor 3 Monaten, 3 Wochen
Kommentar schreiben Diese Antwort melden