Chromsky-Hierarchie

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Chromsky-Hierarchie

      Tag,
      schreibe morgen eine LK-Informatik-klausur über die theoretische Informatik, und habe da mal ne Frage.
      Bei Typ1-, Typ2-, und Typ3-Grammatiken: Worauf genau bezieht sich da das "kontextsensitive"(Typ 1),"kontextfreie"(Typ 2),bzw. "reguläre"(Typ 3) Grammatik? Bezieht sich das reguläre darauf, das der Aufbau der Produktionsregeln immer der gleiche ist, also immer Terminalsymbol und Nichtterminalsymbol(bei rechtsregulärer, andersrum bei linksregulärer Grammatik)? Bei dem Rest hab ich nich wirklich nen Plan worauf sich das bezieht.
      Danke, falls mir wer helfen kann.

      Grüße

    • also es gibt CH-0 bis CH-3, am intuitivsten kann man sich die Grammatiken so vorstellen, dass sie jeweils die Sprache sind die ein spezieller Automat erzeugen kann:
      CH-3 regulär -> endlicher Automat kann diese Sprache erzeugen, die zugehörige Grammatik sind reguläre Ausdrücke (regular expressions) wie a*b* Die Limitierung dieser Grammtik ist das sie nicht zählen kann (also Wörter aus a und b mit anzahl a>b geht nicht) Die Produktionsregeln kennste ja schon
      Hmm jetzt wirds mir zuviel schreibarbeit, lies doch mal den wikiartikel de.wikipedia.org/wiki/Chomsky-Hierarchie
      CH-2 nichtdeterministische Kellerautomaten
      CH-1 deterministische Turingmaschine
      CH-0 nichtdeterministische Turingmaschine

      Also jeder der Stufen erlaubt eine gewisse "flexibilität" der Wörter die die Sprache erkennt (von garnicht "Speichern" koennen bis alle rkursiv aufzählbare Sprachen), daher gibt es spezielle Regeln wie die Grammatiken die Sprache erzeugen dürfen (siehe wiki) und spezielle Maschinendie genau diese Menge an Sprachen erkennen können. Klar?

    • Jo das Prinzip davon ist mir ja auch klar, auch welche Maschinen für was zuständig sind. Mir war nurnoch ganz klar worauf sich das kontextsensitiv und kontextfrei bezieht, was damit ausgedrückt werden soll genau. Wird mir aus dem Wikipediaartikel auch nicht ganz klar. Also bei Typ 2 z.B., man hat in den Produktionsregeln immer ein Nichtterminalsymbol, welches definiert wird durch beliebig viele Terminal- und Nichtterminalsymbole, aber was ist daran kontextfrei?
      Hoffe jetzt ist klarer, worauf meine Frage abzielt.

    • zum Verständnis: Typ 0 ist das allgemeinste, womit man alles ausdrücken kann. Die anderen Typen mit aufsteigender Nummer sind jeweils Spezifikationen einander, demzufolge weniger allgemein und nicht allumfassend. Also die Menge der t3 Sprachen ist eine Teilmenge der t2 Sprachen und so weiter.

      Ausgehend von der allgemeinen Regelform A->B kann man die Typen so runterbrechen:
      Typ 0 Sprachen sind unbeschränkt
      Typ 1 Sprachen sind Typ 0 Sprachen für die gilt, dass B stets größer gleich A sein muss, die also nicht rückwärts laufen können, aber sie können trotzdem noch das Umfeld einbeziehen (->kontextsensitiv).
      Typ 2 Sprachen sind Typ 1 Sprachen, nur dass A keine Terminale, sondern nur noch Nichtterminale enthalten darf. Die Sprache kann somit nicht mehr den Kontext einbeziehen, ist daher kontextfrei.
      Typ 3 Sprachen als speziellste Form wiederum müssen zusätzlich auf der rechten Seite (B) der Regeln mindestens ein Terminal enthalten.

      schlag mich wenns falsch ist

    • Aleph schrieb:

      zum Verständnis: Typ 0 ist das allgemeinste, womit man alles ausdrücken kann. Die anderen Typen mit aufsteigender Nummer sind jeweils Spezifikationen einander, demzufolge weniger allgemein und nicht allumfassend. Also die Menge der t3 Sprachen ist eine Teilmenge der t2 Sprachen und so weiter.

      Ausgehend von der allgemeinen Regelform A->B kann man die Typen so runterbrechen:
      Typ 0 Sprachen sind unbeschränkt
      Typ 1 Sprachen sind Typ 0 Sprachen für die gilt, dass B stets größer gleich A sein muss, die also nicht rückwärts laufen können, aber sie können trotzdem noch das Umfeld einbeziehen (->kontextsensitiv).
      Typ 2 Sprachen sind Typ 1 Sprachen, nur dass A keine Terminale, sondern nur noch Nichtterminale enthalten darf. Die Sprache kann somit nicht mehr den Kontext einbeziehen, ist daher kontextfrei.
      Typ 3 Sprachen als speziellste Form wiederum müssen zusätzlich auf der rechten Seite (B) der Regeln mindestens ein Terminal enthalten.

      schlag mich wenns falsch ist

      Das klingt vernünftig, und ergibt Sinn von wegen kontextfrei und kontextsensitiv, danke!