0 Daumen
23 Aufrufe

Frage:

Sei ∑ = {a,b} ein Alphabet. Beweisen oder widerlegen Sie die folgenden Aussagen.

1. Es gibt eine Sprache L ⊆∑* , so dass die zu L gehorende Rechtskongruenzrelation L nur
endlich große Klassen hat.
2. Zu jedem n ∈ ℕ \ {0}  gibt es eine Sprache Ln so dass der Index (d.h. die Anzahl der
Aquivalenzklassen) der zu Ln gehorenden Rechtskongruenzrelation Ln genau n ist.
3. Zu jeder Sprache L die von einem DFA A erkannt wird, gibt es unendlich viele weitere DFA,
die die gleiche Sprache erkennen und deren Zustandsanzahlen alle verschieden sind.
4. Wird L von einem DFA erkannt, so auch jede Teilsprache L' mit L'  ⊆ L ⊆ ∑* .
5. Ist L U L' nicht-regular, so sind weder L noch L' regular.
6. Sind fur i ∈ ℕ die Sprachen Li alle regular, so ist  ∩i∈ℕ  Li auch regular.



Vielleicht ein Denkanstoß wäre sehr lieb!

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community