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)
--- reguläre Sprache (http://www.informatikerboard.de/board/thread.php?threadid=3101)

Geschrieben von usabb am 20.06.2016 um 10:10:

  reguläre Sprache

Meine Frage:
Jede Sprache, die von einem nichtdeterministischen Kellerautomaten akzeptiert wird, ist eine reguläre Sprache.

Ist das richtig?

Meine Ideen:
.


Geschrieben von eulerscheZahl am 20.06.2016 um 11:38:

 

Was für eine Sprachklasse ist [latex]a^nb^n[/latex]?
Kann der nichtdeterministische Kellerautomat die Sprache akzeptieren?


Geschrieben von usabb am 20.06.2016 um 12:21:

 

Ist eine kontextfreie Grammatik. Nichtdeterministische Kellerautomat würde die Sprache akzeptieren.


Geschrieben von eulerscheZahl am 20.06.2016 um 12:23:

 

richtig.
Und was heißt das für deine Aufgabe?


Geschrieben von usabb am 20.06.2016 um 12:28:

 

Dass es stimmt


Geschrieben von usabb am 20.06.2016 um 12:36:

 

Dann stimmt doch die Aussage auch:
Für jede Sprache, die durch eine kontextfreie Grammatik definiert wird, kann ein deterministischer Kellerautomat angegeben werden, der genau diese Sprache akzeptiert.


Geschrieben von eulerscheZahl am 20.06.2016 um 12:58:

 

Du gehst in die falsche Richtung:
Behauptung: wenn die Sprache von einen nichtdeterministischen Kellerautomaten akzeptiert wird, ist sie regulär.
[latex]a^nb^n[/latex] wird akzeptiert, ist aber nicht regulär. Das ist ein Widerspruch, die Aussage ist daher falsch.


Geschrieben von usabb am 20.06.2016 um 16:41:

 

danke smile


Forensoftware: Burning Board, entwickelt von WoltLab GmbH