c++.de :: Erklärung zu Chomsky

Unregistrierter

Hallo zusammen auf der Suche nach Erklärung der Chomsky - Hierachie bin ich auf diese Seite gestoßen .

Ich habe das Thema Chomsky - Hierachie ( http://www.c-plusplus.de/forum/287313) durch gelesen . Hab dort auch eben meine Frage dort rein geschrieben danach dachte ich wäre ja vllt besser ein Neues Thema zu erstellen.

Ich verstehe einfach nicht die unterschiede der Typen..

meine Schwierigkeit ist dabei mir das in der Praxis verstehen.
Habe hier paar beispiele: ich weiss nicht zu was ich das zuordnen soll wie ich da vor gehen soll.

l, la, laa, lA, li, lii, lI, lu, Luu, lU, le, lee, lE, lai, lo, loo, lO, lau

welcher typ wäre das?

Zitat:

"1.) Ist meine "Vorstellung" über die vier Typen korrekt:

Typ 0: Jede Grammatik ist automatisch Typ 0. Jede Sprache, die von einer Typ 0 Grammatik erzeugt wurde, kann von einer Turingmaschine akzeptiert werden. Da alle Grammatiken von Typ 0 sind, werden alle Sprachen von Turingmaschinen akzeptiert.

Typ 1: Grammatiken vom Typ 1 heißen kontextsensitiv. Bei ihnen müssen immer gleich viele Buchstaben erzeugt werden. Ein Wort einer kontextsensitiven Sprache lautet zum Beispiel aaabbb. Die Sprache dazu lautet L = {a^n b^n|n > 0}. Alle Typ 1 Grammatiken sind vom Typ 0.

Typ 2: Grammatiken des Typs 2 heißen kontextfrei. Auf der linken Seite steht immer nur ein Symbol. Produktionsregeln sehen also etwa so aus: A -> bA oder A -> aAb. Sie werden von einem Kellerautomaten erkannt.

Typ 3: Grammatiken dieses Typs heißen regulär. Hier ist es wichtig, dass sowohl auf der rechten als auch auf der linken Seite nur ein Buchstabe steht. Pro Produktionsschrit darf also nur ein Buchstabe zum Wort hinzugefügt werden. Produktionsregeln sehen beispielsweise so aus: A -> aB A --> a. Reguläre Sprachen werden von endlichen Automaten akzeptiert. "

Was heisst das bei Typ 3?? also wie ich das verstanden habe MUSS immer zwischen ein Buchstaben rechts und links ein Buchstabe sei?? verstehe ich das richtig?

CStoll Mitglied 20:32:58 06.06.2011 Titel:

Luii schrieb:

l, la, laa, lA, li, lii, lI, lu, Luu, lU, le, lee, lE, lai, lo, loo, lO, lau

welcher typ wäre das?

Gar kein Typ - das ist einfach nur Kauderwelsch

Zitat:

Was heisst das bei Typ 3?? also wie ich das verstanden habe MUSS immer zwischen ein Buchstaben rechts und links ein Buchstabe sei?? verstehe ich das richtig?

Also nachdem ich den Satz zum zweiten Mal lese, verstehe ich nicht wirklich, was damit gemeint sein soll.

Unregistrierter

hmm komisch jetzt bin ich voll durch einander :confused:

ich wollte in einem Text nach diesen bestimmte Kombinationen suchen lassen. Und Bin darauf hin auf Regex gestoßen und hab es damit auch hin bekommen. Nur mir wird gesagt das es kontextsensitive Grammatik ist und nicht Regulärer Ausdruck aber das klappt mit dem Regexx ....

Unregistrierter

Also hier ist eine reguläre Grammatik, die die Sprache

L = {l, la, laa, lA, li, lii, lI, lu, Luu, lU, le, lee, lE, lai, lo, loo, lO, lau }

erzeugt. Man kann für alle Sprachen mit endlich vielen Worten eine solche Grammatik konstruieren, darum sind auch alle endlichen Sprachen regulär. (# soll hier einen Kommentar beginnen, ich habe kommentiert wohin jede Startregel führt). Mich würde aber zu sehr interessieren, wie dein dein regulärer Ausdruck aussieht Luii.

Σ = {a, e, i, u, o, A, E, I, O, U, l, L}
N = { S, C, D, F, G, H, J, K, L, M, N, P, Q, R, T, V, W, X}

Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35	S -> LN # Luu S -> lC # la S -> lD # le S -> lF # li S -> lG # lo S -> lH # lu S -> lP # lau S -> lQ # lai S -> lJ # laa S -> lK # lee S -> lM # loo S -> lN # luu S -> l # l S -> lR # lA S -> lT # lE S -> lV # lI S -> lW # lO S -> lX # lU P -> aH Q -> aF J -> aC K -> eD L -> iF M -> oG N -> uH C -> a D -> e F -> i G -> o H -> u R -> A T -> E V -> I W -> O X -> U

knivil Mitglied 11:24:57 06.08.2012 Titel:

Alle Klammersprachen sind kontextfrei. L = {a^n b^n|n > 0} ist ebenfalls kontextfrei, da eine einfache Klammeregel von oeffnenden und schliessenden Klammern beschrieben wird. Beispiel: "{{}}" ist ein korrekter Klammerausdruck bzw. Element der Sprache.

Zitat:

Ich habe das Thema Chomsky - Hierachie ( http://www.c-plusplus.de/forum/287313) durch gelesen

Liess es bitte in einem Buch ueber theoretische Informatik nach. Gewisse Ding im Thread sind dort undeutlich, vielleicht sogar falsch.