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)
----- Suche regulären Ausdruck/Grammatik für Sprache (http://www.informatikerboard.de/board/thread.php?threadid=3170)

Geschrieben von Karlito am 06.08.2016 um 23:00:

 

Ja, Einspruch: 0010 011010 wird nicht akzeptiert.


Geschrieben von Mathlet am 06.08.2016 um 23:16:

 

Stattgegeben Daumen hoch
Wie ich da nen schönen NEA konstruiere unglücklich
Ich hab bisher eigentlich nur DEAs konstruiert und nen gegebenen NEA mit dem Potenzmengenalgorithmus auf nen DEA reduziert. Ist das konstruieren eines NEAs einfacher? Dann wäre es sicherlich die bessere Herangehensweise.
NEA --- Potenzmengenalgorithmus ---> DEA --- Table-Filling-Algorithmus ---> min. DEA


Geschrieben von Karlito am 06.08.2016 um 23:39:

 

Ja, der NEA ist einfacher.

Ich habe einen (Irrtum nicht ausgeschlossen) aber ich glaube es gibt einen einfacheren. Die Potenzmengenkonstruktion wird so recht groß.

Die finalzustände sind absichtlich erstmal "falschherum" gewählt. Durch Komplementbildung erhalten wir am Ende den DEA für die Aufgabenstellung. Komplement darf erst nach der Konstruktion des DEA gebildet werden.

Gruß,

Karlito


Geschrieben von Karlito am 07.08.2016 um 00:34:

 

Wird heute erstmal nix. Bin zu unkonzentriert und müde.

Ich setze mich morgen noch einmal an das Problem.

Gruß,

Karlito


Geschrieben von Mathlet am 07.08.2016 um 09:35:

 

Kein Ding! Vielen Dank schon mal für deine Hilfe und auch die von eulerscheZahl!
Ihr habt mich zu einer vermutlich richtigen Lösung geführt Daumen hoch
Hab gestern auch mal den regulären Ausdruck gemacht... großes Grinsen
Die Grammatik hab ich mir erst mal gespart...


Geschrieben von Karlito am 07.08.2016 um 09:42:

 

Gut, dann setze ich mich da nicht noch einmal ran?

Gruß,

Karlito


Geschrieben von Mathlet am 07.08.2016 um 12:26:

 

Ich glaube, mein Graph müsste jetzt endgültig passen. Also danke, du musst dir nicht noch einmal extra die Mühe machen!
Nur noch kurz die Frage: Ich hab das richtig verstanden, dass ich mit diesem Graph eines DEA ja auch schon bewiesen habe, dass die Sprache definitiv regulär ist, richtig?


Geschrieben von Karlito am 07.08.2016 um 12:47:

 

Naja, schon wenn du einen NFA angeben kannst, ist die Sprache regulär. Hier wäre die Argumentationskette so, dass man einen NFA für die Komplement-Sprache angeben kann. Da NFA regulär sind und reguläre Sprachen unter Komplement abgeschlossen sind, ist die Sprache regulär.

Gruß,

Karlito


Forensoftware: Burning Board, entwickelt von WoltLab GmbH