Chomsky Problem
Torsten Bernstein
Von welchem Chomsky Typ und Chomsky Typ der Sprache ist die folgende Grammatik
A->Bb
B->aC
C->c
Grammatik CH-2 und die Sprache CH-3 nach Lösung. Wieso ist die Sprache 3 und nicht 2 ?
---------------------------------------
BC->a ist diese Regel kontextsensitiv ? längenbeschränkt ist sie nicht. Also müßte die Grammatik CH-0 sein
----------------------------------------
cB->Bc längenbeschränkt und nicht kontextsensitiv ?
Gruß T
Martin Fuchs
> Von welchem Chomsky Typ und Chomsky Typ der Sprache ist die folgende Grammatik
>
> A->Bb
> B->aC
> C->c
Die Angabe von drei Regeln bestimmt noch keine Grammatik!
Insbesondere ohne Angabe des Startsymbols, kann man nur
i.A. nur mutmaßen, hier ist es jedoch sogar egal, welche Variable
Startsymbol ist.
Auf allen linken Regelseiten kommen nur Variablen vor,
also ist die Sprache /mindestens/ CH-2 (kontextfrei).
Die Regel "A->Bb" widerspricht der Forderung für CH-3-Grammatiken
(als rechte Seite kommen nur einzelne Terminalzeichen oder Terminalzeichen
gefolgt von einer Variable vor), demnach ist die Grammatik formal
nicht vom Typ 3.
> Grammatik CH-2 und die Sprache CH-3 nach Lösung. Wieso ist die
> Sprache 3 und nicht 2 ?
Bestimme doch mal den Sprachschatz der Grammatik.
Kannst du vielleicht eine einfachere Grammatik angeben,
die dazu noch CH-3 ist?
> BC->a ist diese Regel kontextsensitiv ?
> cB->Bc längenbeschränkt und nicht kontextsensitiv ?
Wie lauten denn deine Definitionen von kontextsensitiv/längenbeschränkt?
Kannst du dir diese Fragen vielleicht selbst beantworten?
mf