Gramática (autómata)

Una gramática ("G") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = { NT, T, S, P }

donde

NT es el conjunto de elementos No Terminales
T es el conjunto de elementos Terminales
S es el Símbolo inicial de la gramática
P es el conjunto de Reglas de Producción

Clasificación de las gramáticas según Padilla

Según Padilla las gramáticas se clasifican de acuerdo a las reglas de sustitución y nunca se pasa autómatas 2:

Tipo 0 o "No restringida o recursivamente enumerables"

“x puede ser sustituido por y si x está, ya sea, en los símbolos No Terminales o los símbolos Terminales, sin incluir la cadena vacía e y está en los símbolos No Terminales o Terminales, incluyendo la cadena vacía.”

Los lenguajes generados por este tipo de gramáticas se llaman "lenguajes sin restricciones"

Nota: "+" significa "sin incluir la cadena vacía" y "*" significa "incluyendo la cadena vacía". "/" significa "o"

Estos lenguajes también son denominados "recursivamente enumerables"

Las máquinas que los aceptan son las máquinas de Turing (y equivalentes no deterministas)

Tipo 1 o "Sensible al contexto"

“α puede ser reemplazado por β si la longitud de α es menor o igual a la longitud de β, siendo α un símbolo Terminal o una cadena vacía z₁, seguido de un símbolo No Terminal X, seguido de otro símbolo Terminal o una cadena vacía z₂. En el caso de β, z₁ debe ser el mismo símbolo z₁ de α seguido de un símbolo No Terminal o Terminal sin ser la cadena vacía, seguido del símbolo z₂.”

Las máquinas que los aceptan son autómatas linealmente acotados(linear-bounded).

Tipo 2 o "libre de contexto"

“x puede ser reemplazado por y si x pertenece a los símbolos No Terminales e y es un Terminal o No Terminal, incluyendo la cadena vacía.”

Máquinas que los pueden leer:

Máquinas que los aceptan: Autómata a Pila (Pushdown Automaton)

Tipo 3 o "Regular"

También llamada "De contexto regular"

“α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3:

Un símbolo Terminal no nulo seguido de un No Terminal.
Un símbolo No Terminal seguido de un símbolo Terminal no nulo.
Un símbolo Terminal pudiendo ser la cadena vacía.”

Máquinas que los aceptan: autómata finito, determinista o no determinista.

Véase también

Otra explicación: Jerarquía de Chomsky.
Gramática formal.

Datos: Q5884181