Gramáticas
Una gramática para estructura de expresiones G es una 4-ada (V, S,
vo, 
), donde V
es un conjunto finito, S es un subconjunto de V, vo
V - S y
es una relación finita en
V*. La idea es que S es, como ya se ha analizado, el conjunto de
todas las "palabras" permitidas en el lenguaje, y V consta de S
además de algunos otros símbolos. El elemento vo de V es un punto de
partida para para las sustituciones, que serán analizadas en breve. Por último, la relación
sobre V* especifica
los reemplazos permisibles, en el sentido de que, si w
w', se puede reemplazar w
con w' siempre que aparezca la cadena w, ya sea sola o como subcadena de alguna
otra cadena. Tradicionalmente, a la proposición w
w' se la llama producción
de G. Entonces, w y w' son los lados izquierdo y derecho
de la producción, respectivamente. Supóngase que ninguna producción de G tiene a la
cadena vacía 
como lado izquierdo. Es la
relación de producción de
G.
Sea G = (V, S, vo, )
una gramática para la estructura de oraciones. G es de
Tipo 0 si no se establecen restricciones sobre las producciones de G.
Tipo 1 si para cualquier producción w1
w2 , la longitud de
w1 es menor o igual que la longitud de w2 (donde la
longitud de una cadena es el número de palabras en esa cadena).
Tipo 2 si el lado izquierdo de cada producción es un único símbolo no terminal y el
lado derecho consta de uno o más simbolos.
Tipo 3 si el lado izquierdo de cada producción es un único símbolo no terminal y el lado
derecho tiene uno o más símbolos, incluyendo a lo más un símbolo no terminal, que debe estar
en el extremo derecho de la cadena.
Alberto Pacheco
http://www.socrates.itch.edu.mx/~apacheco/teoria/gramatic.htm
Ultima actualización: Mzo 1, 1999