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!
