Clasificación de Chomsky de gramáticas

Según Noam Chomosky, hay cuatro tipos de gramáticas: tipo 0, tipo 1, tipo 2 y tipo 3. La siguiente tabla muestra cómo se diferencian entre sí:

Tipo de gramática	Gramática aceptada	Idioma aceptado	Autómata
Tipo 0	Gramática sin restricciones	Lenguaje recursivamente enumerable	Máquina de Turing
Tipo 1	Gramática sensible al contexto	Lenguaje sensible al contexto	Autómata delimitado lineal
Tipo 2	Gramática libre de contexto	Lenguaje libre de contexto	Autómata de empuje
Tipo 3	Gramática regular	Lenguaje habitual	Autómata de estado finito

Eche un vistazo a la siguiente ilustración. Muestra el alcance de cada tipo de gramática:

Tipo - 3 gramática

Type-3 grammarsgenerar lenguajes regulares. Las gramáticas de tipo 3 deben tener un solo no terminal en el lado izquierdo y un lado derecho que consta de un solo terminal o un solo terminal seguido de un solo no terminal.

Las producciones deben estar en la forma X → a or X → aY

dónde X, Y ∈ N (No terminal)

y a ∈ T (Terminal)

La regla S → ε está permitido si S no aparece en el lado derecho de ninguna regla.

Ejemplo

X → ε 
X → a | aY
Y → b

Tipo - 2 gramática

Type-2 grammars generar lenguajes libres de contexto.

Las producciones deben estar en la forma A → γ

dónde A ∈ N (No terminal)

y γ ∈ (T ∪ N)* (Cadena de terminales y no terminales).

Estos lenguajes generados por estas gramáticas son reconocidos por un autómata pushdown no determinista.

Ejemplo

S → X a 
X → a 
X → aX 
X → abc 
X → ε

Tipo - 1 gramática

Type-1 grammarsgenerar lenguajes sensibles al contexto. Las producciones deben estar en la forma

α A β → α γ β

dónde A ∈ N (No terminal)

y α, β, γ ∈ (T ∪ N)* (Cadenas de terminales y no terminales)

Las cuerdas α y β puede estar vacío, pero γ no debe estar vacío.

La regla S → εestá permitido si S no aparece en el lado derecho de ninguna regla. Los lenguajes generados por estas gramáticas son reconocidos por un autómata acotado lineal.

Ejemplo

AB → AbBc 
A → bcA 
B → b

Tipo - 0 gramática

Type-0 grammarsgenerar lenguajes recursivamente enumerables. Las producciones no tienen restricciones. Son cualquier gramática de estructura de fase, incluidas todas las gramáticas formales.

Generan los lenguajes que son reconocidos por una máquina de Turing.

Las producciones pueden ser en forma de α → β dónde α es una cadena de terminales y no terminales con al menos un no terminal y α no puede ser nulo. β es una cadena de terminales y no terminales.

Ejemplo

S → ACaB 
Bc → acB 
CB → DB 
aD → Db