Chomsky - Hierarchie
-
Hallo zusammen,
ich habe zwei Fragen zur Chomsky - Hierarchie. Wir haben diese Thematik in der Schule durchgenommen und es gibt darüber viele Informationen im Internet, die ich aber nicht alle verstehe. Deswegen habe ich mir einiges zusammengeschrieben.
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.
2.) Welchen Vorteil habe ich, Grammatiken so einzuordnen. Dient es nur zur Klassifizierung? Welchen Vorteil habe ich, wenn ich weiß, dass eine Sprache kontextsensitiv ist?
3.) Ein Kellerautomat akzeptiert kontextfreie Sprachen. Als Beisopiel wurde diese Sprache gegeben: L = {a^n b^n | n>0}
Warum ist eine kontextfreie Sprache? Ich halte sie für eine kontextsensitive Sprache, weil die Buchstabenbanzahl immer gleich ist. Es gibt Übergänge wie S -> aSb.
Vielen Dank
lg, freakC++
-
freakC++ schrieb:
Ein Wort einer kontextsensitiven Sprache lautet zum Beispiel aaabbb. Die Sprache dazu lautet L = {a^n b^n|n > 0}.
Ok, das merke ich mir.
freakC++ schrieb:
3.) Ein Kellerautomat akzeptiert kontextfreie Sprachen. Als Beisopiel wurde diese Sprache gegeben: L = {a^n b^n | n>0}
Warum ist eine kontextfreie Sprache?Jetzt machst Du mich aber durcheinander.
-
Mir ist dieser Widerspruch schon aufgefallen. Daher frage ich nach, wo der Fehler liegt. In meiner Vorstellung von einer kontextsensitiven Sprache oder in meiner Vorstellung eines Kellerautomaten.
In meinem Heft habe ich eben gelesen, dass Kellautomaten kontextsensitive Sprachen akzeptieren. Also keine kontextfreien. Das würde auch zu meiner Vorstellung passen, denn mit der Chomsky - Hierarchie war ich mir recht sicher. Die gennante Sprache L ist meiner Ansicht nacht kontextsensitiv.
Danke
-
Nein, die Sprache ist kontextfrei:
S->ab | aSb
ist eine zugehörige kontextfreie Grammatik.
-
freakC++ schrieb:
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.
Das stimmt IMO nicht. Laut Wikipedia sind Typ-0-Sprachen nicht rekursiv, sondern nur rekursiv aufzählbar, d.h. es gibt Turing-Maschinen, die sie akzeptieren, aber keine, die zusätzlich auch erkennen, wenn ein Wort nicht in der Sprache enthalten ist. Daraus folgt, dass das Komplement einer Typ-0-Sprache (also alle Wörter, die nicht in der Sprache enthalten sind) in der Regel nicht Typ-0 ist.
Typ 1: Grammatiken vom Typ 1 heißen kontextsensitiv. Bei ihnen müssen immer gleich viele Buchstaben erzeugt werden.
Das heißt? Es gibt zwei (AFAIK äquivalente) Definitionen für Typ 1, die monotonen Grammatiken und die kontextsensitiven Grammatiken. Monoton heißt, bei jeder Ableitung muss die rechte Seite länger sein als die linke. Kontextsensitiv heißt, dass bei jeder Regel nur ein Symbol ersetzt wird, und dass dabei der Kontext erhalten bleibt, z.B. wäre vAw -> vBCw oder vAw -> vw solch eine Regel.
Da beide Arten von Grammatiken die gleichen Sprachen erzeugen, ist es auch teilweise üblich, die Begriffe monoton und kontextsensitiv austauschbar für beide Arten von Grammatiken zu verwenden.BTW wenn ich du wäre, würde ich mir das nicht glauben und selbst nachlesen, es gibt da noch ein paar Spitzfindigkeiten, die ich keine Lust hab nachzuschlagen und hier unerwähnt lasse
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.
Das kanonische Beispiel einer Typ-1-Sprache ist eigentlich {a^n b^n c^n | n in IN }. Dein Beispiel ist auch Typ-2.
2.) Welchen Vorteil habe ich, Grammatiken so einzuordnen. Dient es nur zur Klassifizierung? Welchen Vorteil habe ich, wenn ich weiß, dass eine Sprache kontextsensitiv ist?
Na zum Beispiel hilft es dir, das richtige Werkzeug auszuwählen, wenn du einen Parser für die Sprache schreiben willst. Zum Beispiel würdest du nie auf die Idee kommen, HTML mit regulären Ausdrücken parsen zu wollen. Das wird immer wieder gerne versucht, aber ist zum Scheitern verurteilt.
-
ups, verlesen.
-
freakC++ schrieb:
Mir ist dieser Widerspruch schon aufgefallen. Daher frage ich nach, wo der Fehler liegt. In meiner Vorstellung von einer kontextsensitiven Sprache oder in meiner Vorstellung eines Kellerautomaten.
In meinem Heft habe ich eben gelesen, dass Kellautomaten kontextsensitive Sprachen akzeptieren. Also keine kontextfreien. Das würde auch zu meiner Vorstellung passen, denn mit der Chomsky - Hierarchie war ich mir recht sicher. Die gennante Sprache L ist meiner Ansicht nacht kontextsensitiv.
Danke
Also ich bringe heute einen anderen Ansatz um Leuten die Chomsky Hierarchie beizubringen - aus der System Theorie mit Reflektion des Compiler bzw Compiler-Compiler, Cross-Compiler und N'-Compiler Design.
Lade Dir doch mal AtoCC herunter. Aus den Kontext verstehst Du den Zusammenhang von reg. kontextfreien, kontextsensitiven und rekusive aufzählbaren Sprachen besser und die Bedeutung der Gliederung wird klarer. Macht Spaß und man kann eine Menge lernen.
http://www.atocc.de/P.S.: Gute Schule, wo sowas besprochen wird.
-
Prof84 schrieb:
[
Also ich bringe heute einen anderen Ansatz um Leuten die Chomsky Hierarchie beizubringen - aus der System Theorie mit Reflektion des Compiler bzw Compiler-Compiler, Cross-Compiler und N'-Compiler Design.Was?
-
Bashar schrieb:
Zum Beispiel würdest du nie auf die Idee kommen, HTML mit regulären Ausdrücken parsen zu wollen. Das wird immer wieder gerne versucht, aber ist zum Scheitern verurteilt.
wer macht denn sowas??
HTML ist ja schon von haus aus kontextfrei, da ja alle befehle geöffnet und auch geschlossen werden...@freakC++:
erstmal ist es so, dass man die hierarchie wie die zahlenmengen als einen kreis aufbauen kann. damit meine ich, dass es einen kleinen kreis gibt(die regulären sprachen), diese sind in den kontextfreien enthalten (und zusätzlich noch viele weitere), diese wiederum sind in den kontextsensitiven sprachen enhalten (wie auchw eitere sprachen), und die sind alle in Typ0 sprachen enthaltensprich: alles was du mit einem regulären ausdruck oder einem endlichen automaten machen kannst, ist auch durch eine turingmaschine, kellerautomaten oder kellerautomaten(das sidn glaub ich die Typ1 maschinchen?!? oder) möglich...
das ding ,warum man das unterteilt und auch nicht immer das stärkste werkzeug wählt (warum man also quasi nicht einen compiler schreibt der wie eine turingmaschine arbeitet, obwohl man eigentlich nur einen endlichen automaten braucht), ist der performance aspekt !
warum braucht der compiler immer so lange den C++ code zu compilen?
weil C++ nicht mehr kontextfrei ist.reguläre sprachen sind sauschnell (denke an RegEx), kontextfreie sind shcon langsamer (glaube sowas bei O(n²) beim wortptoblem), kontextsensitive haben beim wortproblem was exponentielles (O(2n)) und bei typ0 sprachen ist es nicht mehr entscheidbar... (ich erhebe keinen anspruch auf richtigkeit dieser aussage, die theo inf klausur ist schon vorbei und ich habs nicht mehr alles so 100%ig im kopf)
aber wenn dich das interessiert, ich kann dir den Witt empfehlen mit den Grundlagen der theoretischen informatik (super geil geschrieben, trotz einiger kleiner fehlerchen
und auch en saucooler typ)
-
Skym0sh0 schrieb:
warum braucht der compiler immer so lange den C++ code zu compilen?
weil C++ nicht mehr kontextfrei ist.Dass eine Variable vor ihrer Verwendung deklariert werden muss, ist ein schönes Beispiel für eine Kontextsensitive Grammatik. Aber die C++ Grammatik ist nicht so aufgebaut weil man sich ein Parsen mit exponentieller Laufzeit nicht erlauben kann. Stattdessen wird wohl eher mittels Symboltabellen und Semantischer Analyse geprüft, ob eine Variable deklariert wurde.
Selbst für Kontextfreie Grammatiken kann das Wortproblem im Allgemeinen (soweit ich mich erinnere) nur in O(n³) mittels CYK-Algorithmus entschieden werden. Schon das ist furchtbar langsam weshalb nur Teilmengen (LL, LR, LALR) der kontextfreien Grammatiken praktische Relevanz haben. Für die Ausnahmen wird eben getrickst und man versucht nicht jedes syntaktische Detail einer Sprache in einer Grammatik unterzubringen.
Ich empfand die Chomsky-Hierarchie immer als sehr willkürlich. Oder kennt jemand Gründe woraus sich diese 4 Klassen ganz natürlich ergeben?
-
Skym0sh0 schrieb:
warum braucht der compiler immer so lange den C++ code zu compilen?
weil C++ nicht mehr kontextfrei ist.Der C++ Parser ist nicht das Problem, das ist noch ziemlich fix zu parsen wie gerade gesagt wurde. Und wenn du dir mal Compilezeiten von C++-Programmen anschaust, dann wirste ziemlich schnell merken, was die Auslöst: templates. Aber nicht das Parsen, sondern die Codegenerierung. Würde das Parsen so lange dauern würde keine IDE Codeparser anbieten.
-
µ schrieb:
Ich empfand die Chomsky-Hierarchie immer als sehr willkürlich. Oder kennt jemand Gründe woraus sich diese 4 Klassen ganz natürlich ergeben?
also ich sag immer:
- typ3 wenn man nicht zählen muss
- typ2 wenn man einmal zählen muss
- typ1 wenn man mehrmals zählen muss
- typ0 wenn man alles muss
-
otze schrieb:
Und wenn du dir mal Compilezeiten von C++-Programmen anschaust, dann wirste ziemlich schnell merken, was die Auslöst: templates. Aber nicht das Parsen, sondern die Codegenerierung. Würde das Parsen so lange dauern würde keine IDE Codeparser anbieten.
Das ist nicht ganz korrekt, siehe zum Beispiel: http://yosefk.com/c++fqa/web-vs-c++.html#misfeature-3
Es gibt C++-Code, bei dem man zwingend die Semantik (inklusive vollständiger Auswertung von templates) in Betracht ziehen muss, alleine um den Code richtig parsen zu können.
-
Christoph schrieb:
Das ist nicht ganz korrekt, siehe zum Beispiel: http://yosefk.com/c++fqa/web-vs-c++.html#misfeature-3
Es gibt C++-Code, bei dem man zwingend die Semantik (inklusive vollständiger Auswertung von templates) in Betracht ziehen muss, alleine um den Code richtig parsen zu können.Ja, aber da sist egal, das ist ne handvoll streng limitierter Anwendungen. Das separat abzufangen ist kein Aufwand. Das ist halt ne zelle in deinem LR-Parser in denen 2 Anweisungen stehen. Das macht aber das Parsen nicht np-vollständig (was Kontext-sensitivät nunmal bedeuten würde)
-
otze schrieb:
Christoph schrieb:
Das ist nicht ganz korrekt, siehe zum Beispiel: http://yosefk.com/c++fqa/web-vs-c++.html#misfeature-3
Es gibt C++-Code, bei dem man zwingend die Semantik (inklusive vollständiger Auswertung von templates) in Betracht ziehen muss, alleine um den Code richtig parsen zu können.Ja, aber da sist egal, das ist ne handvoll streng limitierter Anwendungen. Das separat abzufangen ist kein Aufwand. Das ist halt ne zelle in deinem LR-Parser in denen 2 Anweisungen stehen. Das macht aber das Parsen nicht np-vollständig (was Kontext-sensitivät nunmal bedeuten würde)
Wenn der Parser nicht weiß, ob q ein Typ oder ein Wert ist, dann soll er sich also beide Möglichkeiten offen halten, sagst du? Dann kann die IDE aber nicht zur Typdeklaration springen, denn sie weiß dann ja nicht mal, ob es überhaupt ein Typ ist (und wenn ja welcher), oder?
-
Hallo zusammen auf der Suche nach Erklärung der Chomsky - Hierachie bin ich auf diese Seite gestoßen .
ich habe den Beitrag von FreakC++ durch gelesenn
"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?
-
Bei Ch3-Grammatiken sind Regeln der Form A->xB (bzw. A->Bx), A->x oder A->ε erlaubt (mit Nichtterminalen A, B und Terminalen x).
-
Hi hab ein neues Thema erstellt http://www.c-plusplus.net/forum/287903
dort habe ich Beispiel kannst du mir das anhand des beispiel erklären??