reguläre Sprache

Neue Frage »

Auf diesen Beitrag antworten »
usabb reguläre Sprache

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

Ist das richtig?

Meine Ideen:
.
 
Auf diesen Beitrag antworten »
eulerscheZahl

Was für eine Sprachklasse ist [latex]a^nb^n[/latex]?
Kann der nichtdeterministische Kellerautomat die Sprache akzeptieren?
Auf diesen Beitrag antworten »
usabb

Ist eine kontextfreie Grammatik. Nichtdeterministische Kellerautomat würde die Sprache akzeptieren.
Auf diesen Beitrag antworten »
eulerscheZahl

richtig.
Und was heißt das für deine Aufgabe?
 
Auf diesen Beitrag antworten »
usabb

Dass es stimmt
Auf diesen Beitrag antworten »
usabb

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
usabb

danke smile
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »