Gramática (autómata)

De Wikipedia, la enciclopedia libre

Una gramática G desde el punto de vista de un autómata, es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L.

Una gramática es una estructura algebraica formada por 4 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

Tabla de contenidos

1 Clasificación de las gramáticas según Chomsky
2 Tipo 0 o "No restringida"
3 Tipo 1 o "De contexto sensitivo"
4 Tipo 2 o "De contexto libre"
5 Tipo 3 o "De contexto lineal"
6 Véase también

[editar] Clasificación de las gramáticas según Chomsky

Las gramáticas se clasifican de acuerdo a las reglas de sustitución.

[editar] Tipo 0 o "No restringida"

“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 y y está en los símbolos No Terminales o Terminales, incluyendo la cadena vacía.”

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

[editar] Tipo 1 o "De contexto sensitivo"

“α 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 z₂, seguido de otro símbolo Terminal o una cadena vacía z₂. 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₂.”