kontextfreie Spachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ist die Sprache [mm] L=\{a^n b^{2n} | n>0} [/mm] kontextfrei?
Wenn sie kontextfrei ist, müsste man ja einen Kellerautomat damit konstruieren können, aber das geht doch nicht, oder? Denn ich habe doch aufjedenfall zu viele b´s. Oder bin ich gerade auf dem falschen Dampfer?
Sind nicht alle die Sprachen nicht kontextfrei, die nicht gleich viele verschiedene Buchstaben erzeugen? Denn ich schreibe ja immer welche auf den Keller und muss ja im Prinzip mit der gleichen Anzahl an einem oder mehrerer anderer Buchstaben diese wieder vom Keller löschen...? Ich hoffe ihr versteht was ich meine...
Danke um jede Antwort!
LG
|
|
| |
|
Hossa ;)
Ein Wort der Sprache besteht aus n a's, gefolgt von 2n b's. Da die Anzahl n beliebig aber fest ist (n>0), müsstest du dir merken können, wie viele a's vorne an geschrieben wurden. Also hängt die Anzahl der b's vom Kontext ab, also von dem, was vor den b's kam. Daher kannst du hier keine Kontext-freie Grammatik finden.
|
|
|
| |
|
Aber was ist denn mit der Regelmenge P= {S -> aSbb | [mm] \lambda [/mm] } ?
Das ist doch kontextfrei und erzeugt diese Sprache, oder?
|
|
|
| |
|
Hossa ;)
Bei einer kontextfreien Grammatik sind nur Regeln der Form A->a, A->B oder A->aB zugelassen! Andernfalls kann man sie nicht in einem DEA darstellen. Deine Regelmenge ist also gerade keine kontextfreie Grammatik.
|
|
|
|
