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