Clasificación gramatical de Chomsky

Según Noam Homoski, 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 Lenguaje aceptado Máquina
Tipo 0 Gramática ilimitada Lenguaje enumerado de forma recursiva 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 sin contexto Máquina de eyección
Tipo 3 Gramática simple Lenguaje común Máquina de estados finitos

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

Contención Type3, Type2, Type1, Type0

Tipo – 3 gramática

Gramáticas tipo 3 generar lenguajes regulares. Las gramáticas de tipo 3 deben tener un no terminal izquierdo y derecho, que consta de un terminal, o un terminal, seguido de un no terminal.

Los productos deben estar en forma X → a o X → aY

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

y a ∈ T (Terminal)

La regla S → ε permitido si S no aparece a la derecha de ninguna regla.

Ejemplo

X → ε 
X → a | aY
Y → b 

Tipo – 2 gramática

Gramáticas tipo 2 generar lenguajes libres de contexto.

Los productos deben estar en 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 una máquina de hacer estallar no determinista.

Ejemplo

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

Tipo – 1 gramática

Gramáticas tipo 1 crear lenguajes sensibles al contexto. Los productos deben estar en forma

α A β → α γ β

dónde A ∈ N (No terminal)

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

Instrumentos de cuerda α y β puede estar vacío pero γ no debe estar vacío.

La regla S → ε permitido si S no aparece a la derecha de ninguna regla. Los lenguajes generados por estas gramáticas son reconocidos por un autómata acotado linealmente.

Ejemplo

AB → AbBc 
A → bcA 
B → b 

Tipo – 0 gramática

Gramáticas tipo 0 generar lenguajes enumerados de forma recursiva. Las producciones no tienen restricciones. Es cualquier gramática de estructura de fase, incluidas todas las gramáticas formales.

Generan lenguajes que pueden ser reconocidos por la máquina de Turing.

Las actuaciones pueden tener la forma α → β 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 

🚫