Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Unendliche reguläre Sprachen (http://www.informatikerboard.de/board/thread.php?threadid=4274)

Geschrieben von Theorienoob am 17.01.2020 um 16:45:

  Unendliche reguläre Sprachen

Meine Frage:
Gibt es eine unendliche reguläre Sprache, die sich nicht als disjunkte Vereinigung zweier unendlicher regulärer Sprachen darstellen lässt?

Meine Ideen:
Ich habe bisher keine gefunden.


Geschrieben von NixJava am 18.01.2020 um 19:59:

 

Zitat:
Ich habe bisher keine gefunden.

Weil es möglicherweise keine solche Sprache gibt.

Versuch die Aussage mal zu beweisen. Ich denke, das Pumping-Lemma ist dabei der Schlüssel zum Erfolg.

Für jedes [latex]w = uvz[/latex] (mindestens Pumplänge) liegt auch [latex]uv^iz[/latex] in der Sprache. Über dieses [latex]i[/latex] kann man die Menge nun in Klassen einteilen.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH