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:
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.
X → ε X → a | aY Y → b
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.
S → X a X → a X → aX X → abc X → ε
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.
AB → AbBc A → bcA B → b
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.
S → ACaB Bc → acB CB → DB aD → Db
🚫