Chomsky Klassifikation der Grammatiken
Laut Noam Chomosky gibt es vier Arten von Grammatiken - Typ 0, Typ 1, Typ 2 und Typ 3. Die folgende Tabelle zeigt, wie sie sich voneinander unterscheiden -
Grammatiktyp | Grammatik akzeptiert | Sprache akzeptiert | Automat |
---|---|---|---|
Geben Sie 0 ein | Uneingeschränkte Grammatik | Rekursiv aufzählbare Sprache | Turing Maschine |
Typ 1 | Kontextsensitive Grammatik | Kontextsensitive Sprache | Linear begrenzter Automat |
Typ 2 | Kontextfreie Grammatik | Kontextfreie Sprache | Pushdown-Automat |
Typ 3 | Regelmäßige Grammatik | Reguläre Sprache | Endlicher Zustandsautomat |
Schauen Sie sich die folgende Abbildung an. Es zeigt den Umfang jeder Art von Grammatik -
Typ - 3 Grammatik
Type-3 grammarsreguläre Sprachen generieren. Typ-3-Grammatiken müssen auf der linken Seite ein einzelnes Nicht-Terminal und auf der rechten Seite ein einzelnes Terminal oder ein einzelnes Terminal haben, gefolgt von einem einzelnen Nicht-Terminal.
Die Produktionen müssen in der Form sein X → a or X → aY
wo X, Y ∈ N (Nicht terminal)
und a ∈ T (Terminal)
Die Regel S → ε ist erlaubt wenn S erscheint nicht auf der rechten Seite einer Regel.
Beispiel
X → ε
X → a | aY
Y → b
Typ - 2 Grammatik
Type-2 grammars kontextfreie Sprachen generieren.
Die Produktionen müssen in der Form sein A → γ
wo A ∈ N (Nicht terminal)
und γ ∈ (T ∪ N)* (Folge von Terminals und Nicht-Terminals).
Diese durch diese Grammatiken erzeugten Sprachen werden von einem nicht deterministischen Pushdown-Automaten erkannt.
Beispiel
S → X a
X → a
X → aX
X → abc
X → ε
Typ - 1 Grammatik
Type-1 grammarsGenerieren Sie kontextsensitive Sprachen. Die Produktionen müssen in der Form sein
α A β → α γ β
wo A ∈ N (Nicht-Terminal)
und α, β, γ ∈ (T ∪ N)* (Zeichenfolgen von Terminals und Nicht-Terminals)
Die Saiten α und β kann leer sein, aber γ darf nicht leer sein.
Die Regel S → εist zulässig, wenn S nicht auf der rechten Seite einer Regel erscheint. Die durch diese Grammatiken erzeugten Sprachen werden von einem linear begrenzten Automaten erkannt.
Beispiel
AB → AbBc
A → bcA
B → b
Typ - 0 Grammatik
Type-0 grammarsrekursiv aufzählbare Sprachen generieren. Die Produktionen unterliegen keinen Einschränkungen. Sie sind jede Phasenstrukturgrammatik einschließlich aller formalen Grammatiken.
Sie erzeugen die Sprachen, die von einer Turing-Maschine erkannt werden.
Die Produktionen können in Form von sein α → β wo α ist eine Folge von Terminals und Nicht-Terminals mit mindestens einem Nicht-Terminal und α kann nicht Null sein. β ist eine Folge von Terminals und Nicht-Terminals.
Beispiel
S → ACaB
Bc → acB
CB → DB
aD → Db