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 → bTipo - 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 → bTipo - 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