Frage zur Chomsky Hierarchie

Hi,

ich habe eine Frage zur Chomsky Hierarchie. Ich gehe erst in die 11. Klasse und wir haben die Mathematische Notation die bei Wikipedia benutzt wird noch nicht durchgenommen. Daher sagt es mir recht wenig. Ich habe aber versucht so viel wie möglich zu verstehen. Ist Folgendes richtig?

Typ 0 Grammatiken unterliegen KEINEN Einschränkungen.
abcDeFg -> asdCDeeGH
Typ 1 Grammatiken haben auf beiden Seiten eine beliebige Folge von Terminal sowie Nicht-Terminalen.
abcDeFg -> asdCDeeGH
Typ 2 Grammatiken haben auf der linken Seite ein Nicht-Terminal und auf der rechten Seite eine beliebige Folge von terminal sowie Nicht-Terminalen.
A -> abDdSc
Typ 3 Grammatiken haben auf der linken Seite ein Nicht-terminal und auf der rechten Seite entweder ein Terminal, oder ein Terminal und ein Nicht-terminalSymbol.
A->Ab
A->bA
A->c

Wo ist der Unterschied zwischen Typ 0 und Typ 1 Grammatiken?

Vielen Dank

bei Typ 1 muß in jeder Ableitungsregel die rechte Seite mind. so lang wie die linke sein:

w\_1\rightarrow w\_2$ mit $|w\_1| \leq|w\_2|

SG1

infolerner schrieb:

Typ 3 Grammatiken haben auf der linken Seite ein Nicht-terminal und auf der rechten Seite entweder ein Terminal, oder ein Terminal und ein Nicht-terminalSymbol.
A->Ab
A->bA
A->c

Nicht ganz. Bei Typ-3-Grammatiken muss man unterscheiden zwischen linksregulären und rechtsregulären. Das heisst, man hat ENTWEDER Regeln der Form A->Ab ODER Regeln der Form A->bA - aber niemals beide gleichzeitig in einer Grammatik! (Regeln der Form A->c dürfen in beiden Fällen vorkommen)

mal so aus neugier in welcher art von schule bespricht man in der elften klasse compilerbau-grundlagen wie grammatiken?

edv-schule?

Bashar

u_ser-l schrieb:

bei Typ 1 muß in jeder Ableitungsregel die rechte Seite mind. so lang wie die linke sein:
w\_1\rightarrow w\_2$ mit $|w\_1| \leq|w\_2|

Das kenn ich als monotone Grammatik. Kontextsensitive Grammatiken haben nur Produktionen der Form $$\alpha A \beta\rightarrow\alpha \gamma \beta$ mit $\gamma \neq \epsilon$ . Monotone Grammatiken und kontextsensitive Grammatiken sind aber gleichmächtig.
In Wikipedia findet man dazu leider keine Bestätigung, die deutsche Wikipedia nennt monotone Grammatiken kontextsensitiv, die englische erwähnt monotone Grammatiken nicht. Kulturkampf?

BTW wir hatten das auch in der 11.

Vielen Dank.

Eine Frage habe ich noch. Wo ist der Unterschied zwischen Typ 0 und Typ 1?
Mehr als beliebig viele Symbole auf jeder Seite geht doch nicht, oder?

StarCraftFeuerteufel

@shisha: also grammatiken hab ich schon in der schule im informatikunterricht gehabt, auch wenn nicht so detailreich wie dann im studium, aber chomsky hatten wir schon. gut ich war auch auf einem naturwissenschaftlich-mathematischem spezialgymnasium, daran mags vllt liegen. kenne den standardlehrplan leider nicht

Bashar

infolerner schrieb:

Eine Frage habe ich noch. Wo ist der Unterschied zwischen Typ 0 und Typ 1?

Wurde doch schon beantwortet? Typ 1 ist halt gegenüber Typ 0 derart eingeschränkt, dass die rechte Seite einer Produktion aus mindestens sovielen Symbolen bestehen muss wie die linke. Eine Ableitung kann also nicht verkürzen.

Achso, ich hatte deinen Post falsch verstanden.

Vielen Dank für die Hilfe.

infolerner schrieb:

Eine Frage habe ich noch. Wo ist der Unterschied zwischen Typ 0 und Typ 1?

lies mal meine erste Antwort

ach, du bist das schon wieder. Ich muß mir merken, Deine Fragen nicht zu beantworten, schade um die Zeit.

ach, du bist das schon wieder. Ich muß mir merken, Deine Fragen nicht zu beantworten, schade um die Zeit.

Ich dachte, Bashar hätte dir widersprochen und gesagt, dass das was du gesagt hast nur auf monotone Grammatiken zutrifft. Das hatte ich aber auch schon im letzten Post klargestellt.

Achso, ich hatte deinen Post falsch verstanden.

Vielen Dank für die Hilfe.

DU hattest Recht, aber ICH hatte es falsch verstanden. Ich verstehe nicht ganz wo dein Problem ist.

mir hat niemand widersprochen, meine Antwort ist nämlich richtig.

Wie gesagt, schreib bei zukünftigen Fragen dazu, wer du bist, damit ich mir die Zeit sparen kann zu antworten, das ist nämlich immer unerfreulich.

Du willst mich nicht verstehen, oder?
Ich schrieb, dass ich dachte, dass Bashar dir widersprochen hat.
Er hat es aber nicht. Ich hatte seinen Post falsch verstanden. Du hattest Recht.
Das sage ich jetzt zum zweiten mal.

alles klar.