Archiv verlassen und diese Seite im Standarddesign anzeigen : Zuorndung in die Chomsky-Hierarchie?
Hallo!!!
Ich habe nächste Woche meine Prüfung in "Formale Methoden" und bei der Bearbeitung von Vorbereitungsaufgaben bin ich auf ein Problem gestossen, das ich nicht lösen kann.
Es geht um folgende Grammatik:
B->LWR
W->EWa
W->Ea
Ea->Ka
Ka->aKS
SR->Ra
Die Aufgabe ist es, diese Grammatik in Chomsky-Hierarchie einzuordnen. Also die Wahl liegt zwischen Typ1 und Typ0. Denn Typ3 kann es ja nicht sein, denn man hat mehrere Nichtterminalsymbole auf der rechten Seite. Es ist auch nicht Typ2, denn es sind auch mehrere Symbole auf der linken Seite vorhanden. Also bleiben nur Typ1 und Typ0.
Kennt sich vielleicht einer damit besser aus?
Vielen Dank im Voraus!!!
Mfg Djon
maximAL
2006-07-19, 20:54:33
typ 1 sollte das sein.
die regeln sind aber nicht wirklich einheitlich. bei uns sind auch für typ 3 mehrere elemente auf der rechten seite (also ketten von (nicht-)terminalen) erlaubt.
hier ist ein Auszug aus Wikipedia
Typ-3-Grammatiken besitzen entweder nur Regeln, die auf der linken
Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal,
eventuell gefolgt von einem Nichtterminal bestehen (rechtsreguläre Grammatik )
oder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der
rechten Seite aus einem Terminal, eventuell mit vorangestelltem Nichtterminal
bestehen (linksreguläre Grammatik ).
Demnach dürfen die Regeln einer Typ3-Grammatik max. aus 2 Symbolen auf der rechten Seite bestehen.
Worauf machst du es genau fest, dass es eine Typ1-Grammatik ist?
Senior Sanchez
2006-07-19, 21:01:35
Ich würde auch Typ1 sagen, sprich kontextsensitive Grammatik.
Senior Sanchez
2006-07-19, 21:02:48
Djon[/POST]']
Worauf machst du es genau fest, dass es eine Typ1-Grammatik ist?
Weil sie kontextsensitiv ist. Sprich auf der rechten Seite befinden sich auch Nichtterminalsymbole die Wörter sein können die aus allen Zeichen der Alphabete (also sowohl Terminal- als auch Nichtterminalsymbolen) bestehen.
In Abhängigkeit dieser Wörter finden die letztgenannten Produktionen statt und zwar nur wenn der Kontext der dort angegeben ist, auch vorherrscht.
es könnte aber genauso gut eine Typ0-Grammatik sein. Es gibt nicht viele Einschränkungen für Typ1. Eine wäre z.B., dass der linke bzw. rechte Kontext bestehen bleibt. Und das scheint ja hier nicht zu sein.
Senior Sanchez
2006-07-19, 21:13:12
Djon[/POST]']es könnte aber genauso gut eine Typ0-Grammatik sein. Es gibt nicht viele Einschränkungen für Typ1. Eine wäre z.B., dass der linke bzw. rechte Kontext bestehen bleibt. Und das scheint ja hier nicht zu sein.
Ich habe mal in nem anderen Dokument nachgeschaut, da stehts auch so, dass der Kontext erhalten bleiben muss. Somit wäre es dann ne Typ-0-Grammatik.
das ist verständlich, denn jede Typ1-Grammatik ist auch eine Typ0-Grammatik und jede Typ2-Grammatik ist auch eine Typ1 und somit Typ0-Grammatik.
man muss vielleicht noch die Sackgassenbildung untersuchen, denn wenn es zu einer Sackgasse kommt, ist es keine Typ1-Grammatik mehr.
Beispiel:S->ABA
AB->xx
xA->xxxA
A->x
Mit S->ABA->ABx->xBx kommt man in eine Sackgasse rein, daher ist es eine Typ0-Grammatik.
Oder irre ich mich da?
maximAL
2006-07-19, 21:46:21
Senior Sanchez[/POST]']Ich habe mal in nem anderen Dokument nachgeschaut, da stehts auch so, dass der Kontext erhalten bleiben muss. Somit wäre es dann ne Typ-0-Grammatik.
ok, stimmt :frown:
@djon: schau lieber in dein skript als auf wikipedia, denn die definition ist nicht einheitlich
die Definition stimmt mehr oder weniger mit meiner aus dem Skript überein :frown: . Ich hoffe, es kommt was anderes drann ;D
Mfg Djon
Senior Sanchez
2006-07-19, 22:36:22
Ich find Sprachen, Automaten und Grammatiken auch scheiße *g*
Ich mag wikipedia übrigens bei solchen Dingen überhaupt nicht, da ich es viel zu kompliziert erklärt finde, zumindest meistens.
Stone2001
2006-07-19, 23:00:58
Bin ich hier der einzigste der das trivial findet? ;)
Ich würde jetzt sagen, dass die Grammatik Chomsky Typ 1 ist. Als kurze Begründung für diese Behauptung führe ich hier nur mal an, dass die Grammatik erweiternd ist.
Ein formaler Beweis: die Grammatik in Kudora - Normalform:
B -> LX
X -> WR
W -> EY
Y -> WZ
Z -> a
EZ -> KZ
U -> KS
SR -> RZ
Alternativ könnte man auch einen LBA konstruieren.
Stone2001
2006-07-19, 23:11:00
Djon[/POST]']das ist verständlich, denn jede Typ1-Grammatik ist auch eine Typ0-Grammatik und jede Typ2-Grammatik ist auch eine Typ1 und somit Typ0-Grammatik.
man muss vielleicht noch die Sackgassenbildung untersuchen, denn wenn es zu einer Sackgasse kommt, ist es keine Typ1-Grammatik mehr.
Beispiel:S->ABA
AB->xx
xA->xxxA
A->x
Mit S->ABA->ABx->xBx kommt man in eine Sackgasse rein, daher ist es eine Typ0-Grammatik.
Oder irre ich mich da?
Interessantes Problem! Geb mal die Sprache für diese Grammatik an oder die dazugehörige Turingmaschiene! Würde mich jetzt mal interessieren.
maximAL
2006-07-19, 23:26:55
Stone2001[/POST]']Bin ich hier der einzigste der das trivial findet? ;)
Ich würde jetzt sagen, dass die Grammatik Chomsky Typ 1 ist.
SR -> RZ
passt aber nicht.
Magnum
2006-07-20, 15:23:28
maximAL[/POST]']passt aber nicht.
Passt schon!
Eine Typ-1 Grammatik muss nur erweiternd sein! D.h. rechts müssen mehr oder gleichviele Symbol wie links stehen! und bei SR -> RZ ist das schon der Fall!
/dev/NULL
2006-07-20, 16:17:53
Djon[/POST]']
man muss vielleicht noch die Sackgassenbildung untersuchen, denn wenn es zu einer Sackgasse kommt, ist es keine Typ1-Grammatik mehr.
Beispiel:S->ABA
AB->xx
xA->xxxA
A->x
Mit S->ABA->ABx->xBx kommt man in eine Sackgasse rein, daher ist es eine Typ0-Grammatik.
Oder irre ich mich da?
Also ich glaube nur weil es die Möglichkeit gibt in eine Sackgasse zu laufen bedeutet es nicht das es keine TypX Grammatik ist oder? Dieses Wort wird halt einfach nicht erkannt:
S->AB
A->bC
A->b
b->a
ist ne gültige Grammatik und nur weil man mit Produduktion 2 in eine Sackgasse laufen kann heißt das garnichts oder?
Die Sprache dieser Grammatik wäre halt {ba} oder ist das schon zulange her?
Würde auch auf Typ1 tippen: |rechts| >= |links|
Stone2001
2006-07-22, 16:55:33
maximAL[/POST]']passt aber nicht.
hmm, Auslegungssache!
In Kuroda Normalform müssen alle Regeln eine der 4 Formen haben (siehe Schöning - Theoretische Informatik - kurzgefasst Seite 79):
A -> a
A -> B
A -> BC
AB -> CD
Man könnte jetzt darüber Diskutieren, ob SR -> RZ unter die 4. Regel fällt oder nicht, da R auf beiden Seiten vorkommt.
Aber selbst das kann man recht einfach auflösen:
SR -> RZ wird dann zu SR -> AB; AB -> RZ
Diese Regeln entsprechen dann wieder der Kuroda Normalform. Desweiteren muß man aber auch gleich EZ -> KZ auflösen:
EZ -> CD; CD -> KZ
Damit wäre wohl bewiesen, dass die Grammatik vom Typ 1 ist.
(Falls ich mich doch irren sollte, bin ich jetzt schon auf den Gegenbeweis gespannt ;) )
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.