informatica

Autómatas, Gramáticas y Lenguajes
solución de la práctica 2
Elena Gaudioso Vázquez y Tomás García Saiz
Mayo 2012

1. Ejercicio 1
Calculo de los símbolos de preanálisis necesarios.

1.1. Gramática 1
S → xxSzz
S → yxSzz
S → yySzz
S → xySzz
S→λ
En este ejercicio vamos a definir las cuatro palabras, de 4 letras que podemos
generar, todas ellas son generadas por una producción de lagramática diferentes
y en todos los casos terminamos la palabra utilizando la producción S → λ. La
lista de las palabras sería xxzz, xyzz, yyzz, yxzz, como podemos observar los
dos primeros elementos de cada palabra es lo que las diferencian , por lo tanto en
esta gramática necesitamos dos símbolos de preanálisis.

1.2. Gramática 2
S → zzSxx
S → zzSxy
S → zzSyy
S → zzSyx
S→λ
Vamos aconstruir dos palabras de tamaño diferente, zzxx, zzzzxxxx, para
conocer cual es la primera producción que hemos utilizado para construir cada una
de las dos palabras necesitamos leer los dos últimos elementos de las palabras, por
lo tanto el número de símbolos de preanálisis dependerá del tamaño de la palabra,
lo cual quiere decir que potencialmente sería infinito, ∞, lo cual quiere decir
que estagramática es No Determinista y que no se puede resolver con ninguna
cantidad de símbolos de preanálisis.

1

1.3. Gramática 3
S → xSz
S → xySzz
S → xzSzz
S→λ
En esta gramática tenemos producciones que tienen un número diferente de
símbolos terminales antes del símbolo no terminal. Por lo tanto para saber cuantos
símbolos de preanálisis necesitamos nos fijaremos en aquellasproducciones que
tienen más símbolos. En este caso podemos argumentar que si preleemos un xy o
un xz podríamos saber que hemos utilizado una producción o la otra. Para saber
que se ha utilizado la primera producción al tener dos símbolos de preanálisis
debemos de encontrarnos la x perteneciente a la primera producción y la primera
x perteneciente a la siguiente producción aplicada para resolver el noterminal S.
Pero desgraciadamente, si después de utilizar la primera producción S → xSz
hubiéramos utilizado la producción S → λ los dos símbolos de preanálisis
hubieran sido xz y no tendríamos forma de diferenciar si hemos utilizado estas dos
producciones o hemos generado ese par xz con las producciones S → xzSzz. Si
ampliáramos el número de símbolos de preanálisis podríamos encontrar algunasolución parcial, pero el pero de los casos es cuando la primera o la tercera
producción ha sido la última que hemos utilizado, en este caso la única forma
de diferenciarlas es leyendo el número de z que tengamos hasta el final de la
palabra, pero como esto puede ser potencialmente infinito volvemos a tener el
mismo problema que en la gramática anterior. Por lo tanto tenemos una gramática
queno se puede resolver con ninguna cantidad de símbolos de preanálisis.

1.4. Gramática 4
S → ySz
S → xySzz
S → xzSzz
S→λ
Esta gramática al igual que la anterior tiene un número diferente de símbolos
finales en las producciones antes de los no terminales, pero en este caso podemos
reconocer la producción S → ySz sin necesidad de conocer cual es la producción
2

que se ha ejecutado conposterioridad. En este caso volvemos a necesitar dos
símbolos de preanálisis para resolver las producciones, S → xySzz S → xzSzz,
ya que el segundo símbolo de preanálisis es el que las diferenciaría y para saber
si se ha utilizado la primera producción nos fijaríamos en el primer símbolo de
preanálisis de los dos que necesitamos.

1.5. Gramática 5
S → AB
A → xAy
A→λ
B → yBz
B → yz
Altratar esta gramática nos podemos preocupar de saber si se está utilizando
la segunda producción A → xAy o la cuarta producción B → yBz, pero en este
caso no nos tenemos que preocupar de ello, ya que la primera producción nos
esta dando una información adicional que es que no se puede aplicar la cuarta
producción hasta que no se termine de trabajar con el símbolo no terminal A. Por
lo tanto...