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)
--- Nichtdeterministischer Automat (http://www.informatikerboard.de/board/thread.php?threadid=3077)

Geschrieben von wqt121 am 05.06.2016 um 16:01:

  Nichtdeterministischer Automat

Meine Frage:
Jeder nichtdeterministische endliche Automat mit e-Transitionen (e-NEA) kann nur eine endliche Menge von Wörtern akzeptieren.

Ist das richtig oder falsch. Wieso?

Kann mir da jemand helfen?

Meine Ideen:
?


Geschrieben von eulerscheZahl am 05.06.2016 um 17:34:

 

Nehmen wir mal den Automat von der wikipedia als Beispiel.
Der hat zwar keine [latex]\epsilon[/latex] Übergänge, aber das macht keinen Unterschied.
Was wird von diesem Automaten akzeptiert?


Geschrieben von wqt121 am 05.06.2016 um 17:49:

 

also mit den automaten habe ich so meine probleme, aber meint man hier dann die 0,1,1 oder bin ich ganz falsch


Geschrieben von eulerscheZahl am 05.06.2016 um 17:57:

 

Mit einer 0 oder 1 kann man in p bleiben. Bei einer anschließenden 1 kann man in den akzeptierenden Endzustand wechseln. Also wird die Sprache {0,1}*1 akzeptiert. Ist das eine endliche Menge?


Geschrieben von wqt121 am 05.06.2016 um 18:07:

 

wenn die Sprache akzeptiert wird, ist es doch eine endliche Menge oder?


Geschrieben von eulerscheZahl am 05.06.2016 um 18:13:

 

Richtig. Wir haben also durch ein Beispiel die Aussage wiederlegt.


Geschrieben von wqt121 am 05.06.2016 um 18:18:

 

Danke smile


Forensoftware: Burning Board, entwickelt von WoltLab GmbH