1. EJERCICIOS TEMAS 1 Y 2. 1.1.

Construir un analizador para direcciones web del tipo www.nombrededominio.extensión

donde ‘nombrededominio’ es cualquier palabra escrita en caracteres latinos de longitud máxima cinco letras y longitud mínima de dos letras y ‘extensión’ es cualquiera de las terminaciones {es, edu, net}. Se debe procurar que la tabla tenga el menor número de columnas posible. 1.2. Hallar el AFD mínimo y una gramática para el lenguaje dado por la expresión regular r = (a*+bc)bc*+a(b+c) 1.3. Sea Σ = {0 ,1} y sea L = {cadenas que contienen al menos tres unos}. Se pide: a) Encontrar un AFD cuyo lenguaje sea L b) Escribir las ecuaciones regulares que permiten obtener una expresión regular para ese lenguaje. c) Dar un analizador léxico para ese lenguaje (la tabla y un algoritmo).

1.4. Construir un analizador léxico de las matriculas canarias antiguas. Se permiten los formatos: TF-2400-A, GC-2430-GC para matriculas con dos letras finales como mucho se llegó a doblar la G, en ambas provincias. Ejemplo: TF1234-TH no es válida porque le falta el guión después del prefijo provincial TF y porque las dos últimas letras son TH y hemos dicho que lo más lejos que se llegó es hasta GZ. 1.5. Encontrar el AFD mínimo y una expresión regular para el lenguaje de la gramática S:= xA / yA / x / zC / λ A:= yA / xB / zC / x B:= zB / zC / xS / y / z C:= x / y / z 1.6. Dada la gramática regular A:= 0A/ 1C / λ B:= 0C /1D C:= 1A / 0B / 1 D:= 0B / 0 a) Construir el autómata determinista mínimo equivalente b) Obtener una expresión regular que describa su lenguaje.

1.7. Dada la expresión regular r = (ab+c)*(aa*+bb*) © Inmaculada Luengo

U.L.P.G.C.

a) Construir un autómata finito sin λ-transiciones cuyo lenguaje sea el definido por la expresión regular r b) Dar todas las palabras de dicho lenguaje que tengan longitud menor o igual que cuatro. 1.8. Dada la expresión regular

r = ((1* 2) + 3) * + 3*1 + 2 + a) Hallar el autómata finito determinista mínimo cuyo lenguaje viene dado por la expresión regular r. b) Dar todas las palabras de longitud menor o igual que cuatro del lenguaje denotado por r.

1.9. Sobre el alfabeto Σ = {0, 1} sea L = {cadenas que contengan la secuencia 101}. Construir a) Un autómata finito determinista que acepte dicho lenguaje. b) Una expresión regular de L. c) Un analizador léxico para L. 1.10. Sea Σ = {0 ,1} y sea L ={cadenas que contienen un nº de ceros múltiplo de 3} a) Encontrar un AFD cuyo lenguaje sea L b) Escribir las ecuaciones que permiten obtener una expresión regular para ese lenguaje. c) Dar un analizador léxico para ese lenguaje (la tabla y un algoritmo). 1.11. Dada la expresión regular r = (10 + 1) (0 + 01)01* . Encontrar el Autómata Finito Determinista mínimo que lo tiene como lenguaje. *

1.12. Construir un analizador léxico para los números de teléfono canarios: empiezan siempre por 928 o 828 los de Las Palmas y 922 o 822 los de Tenerife, seguidos de 6 dígitos, el primero de los cuales no puede ser un cero. Ejemplo: 828091306 es un teléfono incorrecto, porque a pesar de que el prefijo es uno de los admitidos de la provincia de Las Palmas, el primero de los seis dígitos es un cero; 923281422 es un teléfono incorrecto, porque empieza por 923, que no es ninguno de los prefijos admitidos.

1.13. Hallar el autómata finito determinista mínimo equivalente al siguiente AF

2

© Inmaculada Luengo

U.L.P.G.C.

a a,b

p a

b r

b λ

λ

q a

t a

s

b

1.14. Hallar un AFD para el lenguaje L= palabras con, como mucho, dos símbolos consecutivos iguales, sobre el alfabeto Σ = {0,1}

1.15. Dar un analizador léxico para el lenguaje de los números múltiplos de 4 escritos en forma decimal. 1.16. Construir un analizador léxico que acepte fechas de nacimiento en formato dd/mm/aaaa desde 01/01/1900 hasta 31/12/2007 (Consideramos que febrero siempre tiene 28 días). 1.17. Dada la expresión regular r = (0 + 00 + 01*)1 * +(λ + 01) * a) Construir el AFD mínimo b) Construir una gramática para el lenguaje dado por la expresión regular.

1.18. Dada la expresión regular r = (a + b + c )(b * +c *) + ab * , construir el AFD mínimo para dicho lenguaje, así como una gramática regular equivalente.

1.19. Construir un analizador léxico y una gramática para los múltiplos de 8, escritos en forma binaria. (Algoritmo y datos de entrada). 1.20. Construir un analizador léxico para las cadenas sobre el alfabeto, Σ = {0 ,1,2} que no contienen la secuencia 101. 1.21. Hallar un AFD mínimo equivalente al Autómata de la figura y encontrar una expresión regular para el lenguaje de dicho AFD mínimo.

© Inmaculada Luengo

U.L.P.G.C.

3

0,1 0

p

1

λ

q

r

0 s

0 1

λ,0

t

1

u

λ

1.22. Construir una analizador léxico para las fechas del año 2004, que fue bisiesto, en formato dd/mm/aaaa por ejemplo 29/03/2004. (Algoritmo, tabla, entradas). 1.23. Dada la expresión regular r = (a + bc )(ab + c ) + ca * c * . Hallar a) el AFD mínimo para dicho lenguaje b) una gramática cuyo lenguaje sea r c) todas las palabras del lenguaje de longitud menor o igual a 4. *

1.24. Construir el AFD mínimo para el lenguaje dado por r = (10 ) * 10 * +(10 + 01) *

1.25. Construir un analizador léxico y una gramática para los múltiplos de 8, escritos en forma decimal.

1.26. Construir un analizador léxico para las matrículas europeas del tipo Prefijo nacional_DígitoDígitoDígitoDígito_letra1letra2letra3 donde admitimos los prefijos nacionales de España(E), Alemania (D) y Bélgica (B); letra1 sólo puede ser B, C o D; y letra2, letra3 deben ser consonantes. Ejemplos: E_1234_CRJ es admitida por que cumple todas las condiciones exigidas P1234_HAR no es admitida por varios motivos: i) P no es de los prefijos nacionales admitidos ii) No respeta el guión bajo después de la P iii) la primera letra después de los cuatro dígitos (letra1) no puede ser una H. iv) la segunda letra (letra2) después de los dígitos no puede ser una vocal.

1.27. Construir un analizador léxico para las palabras que tienen como máximo tres símbolos consecutivos iguales, sobre el alfabeto Σ = {a. b}.

1.28. Construir un analizador léxico que acepta la hora en formato digital tal como se indica a continuación: : , donde 4 © Inmaculada Luengo

U.L.P.G.C.

• • • •

puede ser: Mo, Tu, Wed, Th, Fr, Sa, Su. es un número entero que abarca el rango de “00” a “12”. es un número entero que abarca el rango de “00” a “59”. especifica si la hora antes (AM) o después (PM) del mediodía.

Veamos algunos ejemplos de horas aceptadas y NO aceptadas por el analizador . Cadenas aceptadas: Mo 00:00 AM, Tu 12:00 AM, Wed 00:00 PM, Sa 03:15 PM Cadenas NO aceptadas: Mo 19:10 AM, Tu 20:15 PM 1.29. Construir el AFD mínimo para el lenguaje dado por r = (aba + aa )* b + ba * +bb 1.30. Dada la expresión regular r = (01* 0) + (01) a) Escribir todas las palabras de longitud menor o igual que 5. b) Construir el AFD mínimo y dibujarlo. c) Hallar una gramática equivalente. *

*

1.31. Construir el AFD mínimo para el lenguaje denotado por la expresión regular r = (a + b + c )(a + b ) + (ab + bc ) a *

1.32. Dado el Autómata de la figura: 1 0

1

q

p

1 s

0,λ

λ

r

t

1,λ 0

0

0 u

0

a) Encontrar el Autómata Finito Determinista mínimo equivalente (Dar un AFND equivalente, AFD equivalente y aplicar el algoritmo de Moore para encontrar el AFDmín). b) Encontrar una gramática regular que genere el lenguaje descrito por el autómata. 1.33. Sea el alfabeto Σ = {0,1, 2}. Sean los lenguajes L1 = {λ ,11,12}, L2 = {10 ,12 ,012} y

L3 = {1, 2} . Calcular (L1 L3 ) ∪ L2 . −2

1.34. Buscar una expresión regular para el lenguaje de la gramática

© Inmaculada Luengo

U.L.P.G.C.

5

A:= 0A / 0B / 0D / 0 B:= 1C / 1D /1 C:= 1B / 0D / 0 1.35. Una tarjeta permite la apertura de un centro, dependiendo del código escrito en la banda magnética de la misma. El código que abre la puerta ha de contener cadenas no vacías de 0’s, 1’s y 2’s que no contengan los patrones 111, ni 010, ni 212. Diseñar un analizador que detecte y acepte un código válido de apertura de la puerta. (Dar un AFD, alfabeto, tabla y algoritmo). 1.36. Sea Σ = {1,2,3}. Sea L = {ω∈Σ*: ⏐ω⏐= 4 y ω es capicúa}. Construir un analizador léxico para el lenguaje L. (Dar un AFD, alfabeto, tabla y algoritmo). 1.37. Construir un analizador léxico para la hora en formato digital es decir 23:14. la última hora es 23:59, y la siguiente es 00:00 1.38. Construir un analizador léxico para aceptar números reales en todas las formas posibles. Ejemplos: 13.56, -2, 3.21E-3, 3.21E+3, +1.625E3. No son aceptados los números que empiezan por ceros no significativos (ej. -012.56

(

)

1.39. Dada la expresión regular r = ab + bb * + a * (b + ab ) sobre el alfabeto Σ={a,b} a) Construir el AFD mínimo para el lenguaje denotado por r b) Construir una gramática limpia para dicho lenguaje c) Dar todas las palabras de longitud menor o igual que 4 de dicho lenguaje.

(

*

) [( *

)]

1.40. Sea la expresión regular r = 011* 0 1 10 + 11* + 01 a) Construir el AFD mínimo para el lenguaje dado por la expresión regular r. b) Dar todas las palabras ω de dicho lenguaje tales que 5 ≤⏐ω⏐≤ 8.

1.41. Dado el autómata de la figura:

6 © Inmaculada Luengo

U.L.P.G.C.

0

1,λ

0

t

q

1 p

0

s

0 λ

0

r

u

1,λ 1 a) Hallar el AFD mínimo equivalente. (Dar un AFND equivalente, AFD equivalente, y aplicar el algoritmo de Moore para encontrar el AFDmín). b) Encontrar una expresión regular para el lenguaje del AFD mínimo aplicando el teorema de análisis de Kleene.

1.42. Obtener un AF sin transiciones λ que acepte el lenguaje descrito por las expresiones regulares:

(

)

+

+ * + * a) r = a b a + c + cc b b) r = (0+1)*1+ 0 (210* + 1+)

1.43. En un laboratorio se analizan trozos de códigos de ADN humanos. En dicho código pueden aparecer 4 tipos distintos de bases nitrogenadas : Adenina (A), Timina (T), Citosina (C) y Guanina (G) En un experimento se busca si un determinado individuo tiene una determinada “marca genética”. Se dice que un individuo tiene dicha marca si: i) en su muestra de ADN aparece el patrón CGGC y ii) en dicha muestra no hay un número impar de bases del tipo Timina (T). Diseñar un Autómata Finito Determinista (AFD) que detecte, dada la muestra de un individuo, si éste lleva la marca genética citada. 1.44. Dada la expresión regular: r = (00* + 21+)+ (12+)+ + λ, se pide: a) Dar un AFD cuyo lenguaje sea L(r). NOTA: Dar primero un AFND-  luego pasar a un AFND y a continuación a un AFD equivalente. L(r) / | | 4}. b) Dar por extensión el conjunto L = {

1.45. Considérese el siguiente Autómata Finito (AF):

© Inmaculada Luengo

U.L.P.G.C.

7

1

1 p

0 q

0

0

1 r

s

1

0,2

Se pide: a) Plantear las ecuaciones que resuelven el Teorema de Análisis de Kleene. Asimismo, resolver dichas ecuaciones obteniendo así una expresión regular para el autómata de la figura. b) Encontrar un AFD mínimo, aplicando el Algoritmo de Moore, para el AFND de la figura. c) Para el AFD mínimo obtenido, dar un analizador léxico que reconozca su lenguaje.

1.46. Encontrar un Autómata Finito Determinista que acepte como lenguaje cadenas de 0, 1, 2, con las restricciones de que las cadenas: i) no contienen el patrón 002 y ii) no terminen ni comiencen por 1. 1.47. Encontrar un Autómata Finito Determinista que acepte como lenguaje cadenas de 0, 1, 2, con las restricciones de que las cadenas: i) no contienen el patrón 002, ii) no terminen ni comiencen por 1 y iii) si comienzan por 0, que no acaben en 0.

1.48. Para cada una de las siguientes expresiones regulares: r1 = (01*0 + 10*1) (01) 1 *

[

*

*

( ) (01 2) (202) = (10 ) (0 0) + (10 ) (0 + 1) +

r3 = λ + ∅* + 10 + 02 + r4

]

* +

r2 = (01 + 12 ) 2* (3 + 01) * *

*

*

+

+

*

+

Se pide: a) Encontrar un AFND-λ que acepte el lenguaje que denotan. b) Dar el conjunto Li={ω∈L(ri) / 0 ≤ |ω| < 4}.

1.49. Encontrar un analizador léxico que detecte palabras, que representan números en hexadecimal, de forma que i) cada tercer símbolo no haya una letra y ii) si comienza por una letra, no acabe en otra. Ejemplo: A013A2, 1A3 (son aceptadas) y 12AB y B68932160F (no son aceptadas)

8 © Inmaculada Luengo

U.L.P.G.C.

1.50. Encontrar un analizador léxico que detecte palabras, de como mucho 9 símbolos que representan números en hexadecimal, de forma que cada tercer símbolo no haya una letra y que si comienza por una letra, no acabe en otra. Ejemplo: A013A2, 1A3 (son aceptadas) y 12AB y B68932160F (no son aceptadas)

1.51. Dado el siguiente autómata finito: λ A

λ

λ

B λ

D

1

E

0

F

λ

G 1

0

λ

λ

C

H 1

Se pide: a) Minimizar, mediante el algoritmo de Moore, dicho autómata. b) Dar una gramática regular que genere el lenguaje aceptado por dicho autómata finito. c) Resolver las ecuaciones regulares asociadas al AF por el teorema de análisis de Kleene.

1.52. Dado el alfabeto Σ={0,1,2} encontrar un Autómata Finito Determinista que acepte cadenas de Σ* de forma que si el código comienza y termina por el mismo símbolo, no debe contener el patrón 1001. En caso contrario, las cadenas serán aceptadas. * 1.53. Dada la expresión regular r = (ab ) (ab * +b * a ) , se pide dar el Autómata Finito Determinista mínimo que acepte el lenguaje L(r). (Dar un AFND-λ, AFND equivalente, AFD equivalente, y aplicar el algoritmo de Moore para encontrar el AFD mínimo).

1.54. Construir un Analizador Léxico que reconozca cadenas de longitud no nula con símbolos que representan un número en octal, de forma que la paridad de los símbolos “números impares” coincida con la paridad de los símbolos “números pares”, y que no acaben en símbolos de “números pares”. Ejemplos: 031465: tiene 3 símbolos “números pares” y 3 símbolos “números impares”, con lo cual como la paridad es la misma (impar de pares, impar de impares) y no acaba en un símbolo “número par” debería ser aceptada. 3357: paridad de símbolos “números pares” es PAR (cero), e ídem con la de los símbolos “números impares” (cuatro) y no acaba en símbolo “número par”. 7436: no es aceptada porque termina en dígito par

© Inmaculada Luengo

U.L.P.G.C.

9

17467: no es aceptada porque tiene 3 dígitos impares (impar) y dos dígitos pares (par). 1.55. Para la siguiente gramática regular G =({0,1}, {A, B, C, D}, A, P), siendo P las reglas A := 0B | 1C | λ B := 0B | λ C ::= 1C | 0D D ::= 0A | 0B | λ Se pide: a) Encontrar una expresión regular mediante la aplicación de la resolución del Teorema de Análisis de Kleene. b) Dar el conjunto de cadenas de longitud menor que 4 generadas por G.

1.56. Dado Σ={0,1,2}, construir un AFD que acepte los siguientes lenguajes: a) L1 = { cadenas de longitud par que tenga un nº impar de 1} b) L2 = {cualquier cadena excepto aquellas que tengan el patrón "10" si la cadena contiene un número impar de 2} 1.57. Dada la expresión regular: r = (0*(0+0) + 1)*0+ + ∅∗ se pide: a) Dar el AFD mínimo cuyo lenguaje sea L(r). NOTA: Construir primero un AFND-λ luego pasar a un AFND y a continuación a un AFD. Por último, utilizar el Algoritmo de Moore para minimizar el AFD obtenido. b) Dar por extensión el conjunto L = {ω∈L(r) / |ω|≤3}.

1.58. Sea el siguiente Sistemas de Ecuaciones Lineales utilizado por el Teorema de Análisis de Kleene en la búsqueda de una expresión regular de un autómata finito M: xA = 1xA + 0(xC + xB) + λ xB = 0xB + 1(xA + xC) xC = (0 + 2)xC Se pide: a) Dar una expresión regular para L(M). b) ¿Podría considerarse r = 0*1+ como expresión regular? ¿Por qué? c) Analizando el sistema de ecuaciones anterior, ¿de qué tipo de autómata finito se trata? Justificar la respuesta.¿Podríamos reconstruir el autómata M original a partir del sistema de ecuaciones del enunciado? Justificar la respuesta.

1.59. Obtener un autómata finito sin transiciones λ que acepte el lenguaje descrito por las expresiones regulares siguientas. (Recordemos que L+ = L* − { λ} ) r = ( a + b* a + c ) + cc* b* +

a)

10 © Inmaculada Luengo

U.L.P.G.C.

b) r = (0+1)*1+ 0 (210* + 1+)

1.60. Construir un analizador léxico (autómata, tabla, entradas y algoritmo), para las palabras que tienen como máximo tres símbolos consecutivos iguales, sobre el alfabeto Σ = {a,b} .

1.61. Sea el siguiente Sistemas de Ecuaciones Lineales utilizado por el Teorema de Análisis de Kleene en la búsqueda de una expresión regular de un autómata finito M: x0 = bx0 + a(x3 + x1) + λ x1 = ax1 + b(x0 + x3) x2 = (a + c)x2 + bx3 x3 = λ x4 = (a + c)x4 + bx3 + λ Se pide: a) Dar una Expresión Regular que acepte L(M) sabiendo que x0 = L(M). b) Dar el Autómata Finito Determinista Mínimo (AFDmín) que acepte L(M) a partir del Sistema dado, utilizando el Algoritmo de Moore.

1.62. Dar un AFD que acepte como lenguaje: a) L = {cadenas de ceros y unos tal que no contengan un número de par de ceros si acaban en 11}. b) L = {cadenas de a y b tal que la longitud de la cadena sea par y además no acaben en b}

1.63. Dado el alfabeto Σ={a,b,c}, encontrar un Autómata Finito Determinista (AFD) que acepte cadenas de Σ∗ excepto aquellas que contengan el patrón "bcc" si hay más de 2 “a”-es seguidas 1.64. Dado Σ={0,1,2} se considera el lenguaje L = {cadenas de Σ* tal que si aparece el patrón “200” entonces el número de veces en que aparece el 0 en la cadena ha de ser par}. Se pide: a) Dar un Autómata Finito Determinista (AFD) cuyo lenguaje aceptado sea L. b) Dar un analizador léxico para dicho lenguaje (tabla y algoritmo).

(

) ( 2* + 0+ )

1.65. Dada la expresión regular: r = 00+ + 2+1

*

´+

+ λ , se pide:

a) Dar el AFD mínimo cuyo lenguaje sea L(r). (Construir un AFND-λ luego pasar a un AFND y a continuación a un AFD; por último, utilizar el Algoritmo de Moore para minimizar el AFD obtenido). b) Dar por extensión el conjunto L = {ω∈L(r) / |ω| ≤ 3}.

© Inmaculada Luengo

U.L.P.G.C.

11

2. EJERCICIOS TEMAS 3 Y 4. 2.1. Hallar una máquina con salida que, leyendo números en forma binaria, dé como salida el resto (en el sistema decimal) de la división por 6 del número leído hasta ese momento. Ejemplo: Si la entrada fuera 11111, la salida deberá ser 13131; si la entrada fuera 10110, la salida deberá ser 12542.

2.2. Construir un Autómata, que vacíe su pila antes de aceptar cualquier palabra y cuyo lenguaje sea:

{

}

L = x r y 2 r + k z k : r > 0, k ≥ 0

2.3. Construir una máquina con salida tal que en cada momento dé el resto modulo 4 del número leído hasta el momento en el sistema decimal.(Ejemplo si el numero de entrada fuera 15658 la salida de una máquina de Moore sería 013012) 2.4. Construir un Autómata de Pila con el menor número posible de transiciones no deterministas y que vacíe la pila antes de aceptar cualquier cadena, para el lenguaje, sobre el alfabeto Σ = {a,b}, siguiente L = a n b m c m−n : m ≥ n ≥ 0

{

2.5. Dada la gramática siguiente Σ N = {S, A, B} , S es el axioma y P es:

}

G = (Σ T , Σ N , S , P )

donde

Σ T = {x , y} ,

S : = xAy / yBx A: = xAy / xy B: = yBx / yx 2.6. Obtener un Autómata de Pila equivalente a la gramática. a) Describir el lenguaje de la gramática. b) Describir los estados de la pila al procesar la palabra xxxyyy. c) Dar la tabla para un analizador sintáctico para el lenguaje de la gramática.

2.7. Dada la gramática: S:=MN M:=aMc / ac N.=bNc /M / λ a) Obtener una equivalente bien formada b) Obtener una equivalente en forma normal de Chomsky

© Inmaculada Luengo

U.L.P.G.C.

2.8. Diseñar una máquina de Moore con alfabeto de entrada Σ = {0,1} que devuelva como salida: I si la cadena de entrada tiene un número impar de unos, P si la cadena tiene un número par de unos y no acaba en cero y N en los demás casos. 2.9. Hallar un Autómata de pila, que vacíe su pila antes de aceptar ninguna palabra, para el lenguaje L = x n y m z r : m = 2n + r ; m, n > 0, r ≥ 0 (Recordamos que en la pila se puede insertar más de un símbolo de una vez, pero sólo se pueden extraer de uno en uno).

{

}

2.10. Dado el autómata de la figura x,λ;x p y,x;y

y,y;λ q

y,x;x a) Localizar los puntos de no determinismo (si los hay) y explicar en que situaciones se daría el no determinismo. b) Construir un AP equivalente al de la figura que vacíe su pila antes de aceptar cualquier palabra. c) Estudiar su lenguaje con el mayor detalle posible d) Escribir todas las reglas de la gramática equivalente asociadas a la transición δ ( p , y; x ) = ( q , y )

2.11. Dada la gramática G dar un autómata de pila equivalente, estudiar su lenguaje y construir un analizador sintáctico para dicho lenguaje. G = (Σ T , Σ N , P, A) siendo Σ T = {x, y} , Σ N = {A, M , N } y las reglas A:= xMy / Nx / x M:= xxM/x N:= yN / y 2.12. Describir el lenguaje de la gramática siguiente y dar un analizador sintáctico. G (Σ T = {0,1}, Σ N = {A, B, C , D}, A, P ) , siendo las producciones de P A:= 0B0 / 1C1 B:= 1B1 / 0C0 C:= 0C0 / 1 2.13. Construir un AP, que vacíe su pila antes de aceptar cualquier palabra, para el lenguaje con el menor número posible de estados y de transiciones no deterministas.

© Inmaculada Luengo

U.L.P.G.C.

13

{

}

L = a n b m : n ≤ m ≤ 2n

2.14. Construir un analizador sintáctico para la gramática (cuyo axioma es S): S:= xxA / xyB A:= yA / y B:= xBy / y Especificar los datos de entrada del algoritmo correspondiente. 2.15. Depurar la siguiente gramática obtener una equivalente bien formada, obtener otra equivalente en forma normal de Chomsky y dar un analizador sintáctico LL(k), con k mínimo, para su lenguaje. S:= xAz / yBz/ λ A:= xAz / B / λ B:= yBz 2.16. Dada la gramática cuyo axioma es A y sus reglas A:= xyByz / xAx / z B=: yBy /z a) Construir un analizador sintáctico LL(k), con k lo menor posible b) Escribir el lenguaje de dicha gramática c) dar otra equivalente en forma normal de Chomsky.

2.17. Construir un autómata de pila determinista que sólo acepte palabras con la pila vacía, para el lenguaje

{

}

L = x m y n z r : m = 2n + r , m > 0

2.18. Dada la gramática G = (Σ T = {0,1}, Σ N = {A, B ,C , D , E , F }, A, P ) con las reglas A:= 01B / 1C1 / E B:= 1B1 / 1F / 0 / 00 C:= D /1F0 D:= 0D / 1C. E:= 11 / 10 / λ F:= 1D / 1C / 1F0 1.1. Construir una equivalente en forma normal de Chomsky (FNC). 1.2. Construir un analizador sintáctico para el lenguaje de G.

2.19. Construir un Autómata de Pila determinista que sólo acepte palabras con la pila vacía, para el lenguaje L = {a m b m + n c n : m ≥ 0, n ≥ 1}

14 © Inmaculada Luengo

U.L.P.G.C.

2.20. Construir un AP con el menor número posible de transiciones no deterministas y que sólo acepte palabras con la pila vacía, para el lenguaje L = {w :#a ( w) =#b ( w)} donde w ∈ (a + b ) * y #a ( w) = número de veces que el símbolo a aparece en la palabra w. 2.21. Dada la gramática G = (Σ T = {0,1}, Σ N = {A, B, C , D, E , F }, A, P ) con las reglas A:= 0EF / 1A / 1 B:= BF / 1B / 1 C:= 0C /1C D:= 1A1 / 1B1 / 0D. E:= 0 F:= 1B / 01 / 00 a) Construir una gramática equivalente bien formada. b) Construir un analizador sintáctico para el lenguaje de G.

2.22. Hallar una gramática en forma normal de Chomsky equivalente a la siguiente. S:= 0BC1 / 0B / 1A1 A:= 0C1 / A / B / λ B:= 0BB / 1B C:= A1 / B0 / 11 / 0 2.23. Construir una autómata de pila determinista para el lenguaje L = {a n b n : n no es múltiplo de 5} 2.24. Construir un analizador para el lenguaje de la gramática G = (Σ T , Σ N , S , P ) siendo Σ T = {x , y}, Σ N = {S ,A, B} , S el axioma, con las reglas S:= xyAyx / yBx A:= xAx / yBx B:= yBx / λ 2.25. Construir un analizador LL(k) con k mínimo, para el lenguaje

{

}

L = x n y m x n : n ≥ 0, m > 0

2.26. Construir una máquina de Moore que tenga como alfabeto de entrada el conjunto de los dígitos {0,1,...9} y que en cada momento dé cómo salida el resto módulo 3 de la suma de los dígitos leídos hasta ese momento. Ejemplo: si en la cinta de entrada ponemos 1234567, las sumas sucesivas son 1-3-6-1015-21-28, y por tanto la secuencia de salida debe ser 0-1-0-0-1-0-0-1 (donde el primer cero es el símbolo que se escribe al comienzo, sin entrada)

© Inmaculada Luengo

U.L.P.G.C.

15

2.27. Construir una autómata de pila que vacíe su pila antes de aceptar cualquier palabra, cuyo lenguaje aceptado sea L = ω1cω2 :ω1 , ω2 ∈ a + b)*, ω2 ≠ ω1−1

{

(

)}

2.28. Construir un autómata de pila con alfabeto de entrada Σ = {x,y}, con el menor número posible de transiciones no deterministas, con el menor número de estados posible y que vacíe la pila antes de aceptar cualquier palabra, cuyo lenguaje sea

{

}

L(M ) = x r y 2 r + k z k : r , k ≥ 0

2.29. Construir un analizador LL(k) (tabla y algoritmo) con k mínimo, para el lenguaje de la gramática cuyo axioma es A y el conjunto de reglas A:= xxB / yCx, B:= xBy / x; C:= yCx / y. (Escribir paso a paso la construcción de la tabla, cada casilla debe estar justificada). 2.30. Construir un autómata de pila con alfabeto de entrada Σ = {a,b}, con el menor número posible de transiciones no deterministas y con el menor número de estados posible, cuyo lenguaje sea L(M ) = {ω ∈ Σ* : # a (ω ) = # b (ω ) + 1} (Recordemos que #a(ω) = nº de veces que el símbolo a aparece en ω). 2.31. Dada la gramática G con axioma A, ΣT={0,1}, ΣN={A,B,C,D,E}y las reglas A:= BD / C01 / A1 /0D1 B.= B0 / 0E1 / λ C:= 0D1 / 11C / 1 / λ D:= 0D / 1C E:= 1E / 0E1 a) Construir una gramática equivalente bien formada. b) Construir una gramática equivalente en Forma Normal de Chomsky. c) Derivar desde el axioma 5 palabras del lenguaje de G.

2.32. Construir un analizador para L(G), siendo G la gramática con axioma S y reglas S:= MN M:= aMc/ac N:= bNc/M/λ 2.33. Construir una autómata de pila que vacíe su pila antes de aceptar cualquier palabra y cuyo lenguaje aceptado sea L = {a n b n : n ≠ 3 (módulo 4), n > 0}

2.34. Dada la siguiente gramática, con ΣT = {0,1,2,3} y ΣN = {S(ax.), M,N,P,Q,R,T,V}, obtener una equivalente que esté bien formada: 16 © Inmaculada Luengo

U.L.P.G.C.

S := 1Q | V | RS2 | NT T := 0P P := N1 | λ | P | 1T M := 0MS | λ | M1 | T | M Q := Q1 | P N := N1 | 0 V := 3 | S1 2.35. Diseñar una Máquina de Mealy que tomando como cadena de entrada una secuencia de símbolos que representan un número en base 4, proporcione como salida el resto módulo 5 de dicho entero. Construir una Máquina de Moore equivalente a la de Mealy construida. 2.36. Sea ω una cadena de dígitos que representa un número en decimal. Se pide diseñar una Máquina de Moore que, ante la entrada ω produzca como último símbolo de salida “S” si el decimal representado por ω es múltiplo de 3. En caso contrario, deberá dar como último símbolo de salida “N”. Además, el primer símbolo de salida que deberá dar la máquina deberá ser “→”. Ejemplos: Entrada 3 4 2 Salida → S N S

Entrada 9 0 2 0 Salida → S S N N

Entrada 1 5 Salida → N S

2.37. Dado el siguiente Lenguaje : L = {anb2manb2k/ m,n,k > 0}, se pide: a) Encontrar un Autómata de Pila determinista que acepte L. b) Dar además aquellas cadenas de L para n ∈ {1,2}. c) Si se añade la restricción: “m > n”, ¿cómo cambiarían las respuestas de los apartados anteriores?

2.38. Sea G una gramática independiente del contexto cuyo analizador mínimo del tipo LL necesario para reconocerla es un LL(3). Sabiendo que la matriz que utiliza dicho analizador se llama ‘tabla’ y que la gramática G no genera cadenas de orden menor que 3 excepto la cadena vacía, se pide dar un Analizador Sintáctico del tipo LL(3) que reconozca dicha gramática. 2.39. Se pretende encontrar un traductor de códigos que funciona de la siguiente forma: “La salida ante una entrada determinada en binario deberá ser siempre el número decimal que representan los tres primeros bits del binario de entrada, y como resto de símbolos de salida el valor “:” las veces que sea necesario.” Ejemplo: entrada : 101001 -> salida -> “:::5:::” 11111110 -> salida -> “:::7:::::”

© Inmaculada Luengo

U.L.P.G.C.

17

2.40. Encontrar un Autómata de Pila que, dado el alfabeto Σ={a,b} acepte el lenguaje: L = {cadenas de Σ* tal que el número de “a” y de “b” coincidan, que no acaben ni empiecen por el mismo símbolo, y que la longitud de las cadenas aceptadas sea par}. Dar además la traza que sigue la pila ante una cadena abbaabb de L. 2.41. Escribir un algoritmo para un reconocedor sintáctico del tipo LL(4) que reconoce una gramática G que genera la palabra vacía, y que no genera otras palabras de longitud menor que 4. Se supone que la tabla de traducción de reglas está en una matriz de nombre TABLA. 2.42. Definir la Forma Normal de Chomsky (FNC) de una gramática. Como aplicación, encontrar la FNC para la gramática siguiente ΣΝ={A,B,C}, ΣΤ={α,β,γ}, axioma C: C::= ABz / λ A::= Aa / a / λ / AB B::= Bb / A / λ 2.43. Dado el alfabeto Σ={a,b} y el lenguaje L= {palíndromos (capicúas) de Σ* de longitud impar}. Se pide: a) Dar una gramática para L. b) Dar un autómata de Pila para la gramática anterior. (No se aceptan inserciones de más de un símbolo al mismo tiempo en la pila). c) ¿Qué tipo de analizador LL(k) podría usarse para implementar un programa que detecte este lenguaje (decir el valor del k mínimo)?

2.44. Diseñar una Máquina de Mealy sobre el alfabeto de entrada Σ={a,b} de forma que para una entrada w produzca una salida v, en la que el símbolo i-ésimo será 1 si los símbolos i-ésimos e (i-1)-ésimos de w son iguales, y será 0 en caso contrario. Una vez encontrada la máquina pedida, encontrar una Máquina de Moore equivalente a ella. 2.45. Gramáticas : 1.3. Dada la siguiente gramática, con ΣT = {a,b} y ΣN = {S(ax.), A,B}, obtener una equivalente en la FNC (Forma Normal de Chomsky) : S := abAB A := bAB | λ B := BAa | A | λ 1.4. Dada la siguiente gramática, con ΣT = {0,1,2,3} y ΣN = {S,M,N,P,Q,R,T}, axioma S, obtener una equivalente que esté bien formada: S : = M | 0Q | RS1 | MN T := 0P P:= N1 | λ | 1T M := 0MS | λ | M0 | R

18 © Inmaculada Luengo

U.L.P.G.C.

Q:= Q1 N := N1 | 1 2.46. Determinar el analizador sintáctico más simple del tipo LL (tabla y algoritmo) que reconozca el lenguaje generado por la gramática siguiente con ΣT = {a,b,c} y ΣN = {S(ax.), A} y las reglas: S := Sa | aAc | c A := Ab | ba 2.47. Construir un Autómata de Pila, con el menor número posible de transiciones no deterministas, que acepte las cadenas sobre el alfabeto Σ = {a, b}, de forma que el número de símbolos ‘a’ sea el doble de símbolos ‘b’ (Recordamos que está permitido insertar más de un símbolo de una vez en la pila, pero sólo se pueden extraer de uno en uno). L = ω ∈ Σ * : # a (ω ) = 2# b (ω )

{

}

2.48. Construir una gramática bien formada equivalente a la gramática G , con axioma S y las reglas S := A / B A:= aCA B := aCB / aDE C := aCC D := aCD / aDF / b E := λ F := b / λ 2.49. Construir el analizador LL(k) más simple, justificando la elección de k, para la gramática de axioma S y las reglas S := AB A := aA / a B := bBc / bc 2.50. Dado el alfabeto Σ = {0,1} y el lenguaje L= {palíndromos (capicúas) de Σ* de longitud impar}. Se pide: a) Dar una gramática para L. b) Dar un autómata de Pila para la gramática anterior. (No se aceptan inserciones de más de un símbolo al mismo tiempo en la pila. c) ¿Qué tipo de analizador LL(k) podría usarse para implementar un programa que detecte este lenguaje (decir el valor del k mínimo)? 2.51. Dado el alfabeto Σ = {0,1} , se pide a) Dar una gramática para el lenguaje de los capicúas de longitud par.

© Inmaculada Luengo

U.L.P.G.C.

19

b) Construir un Autómata de Pila para dicho lenguaje.

2.52. Dado el alfabeto Σ={0,1} diseñar una Máquina de Moore que devuelva como salida: “P”: si la cadena de entrada tiene un número par de unos, “I”: si la cadena tiene un número impar de unos pero no acaba en cero, “N”: el resto de los casos. Dar además, un modelo de Máquina de Mealy equivalente. *

2.53. Encontrar una Máquina de Moore que para una entrada w∈(x+y) , produzca como salida: A si la cadena acaba en yxy, B si la cadena tiene un número impar de y, y C en cualquier otro caso. (En caso de ambigüedad, prevalecerá la prioridad del orden de la salida según la secuencia de A a C). 2.54. Dada la gramática: S: = xSy | xyTyz T: = λ Z: = xSy | T Se pide: a) Estudiar, y en su caso encontrar, si la gramática admite la Forma Normal de Chomsky (FNC), justificando la respuesta. ¿Se trata de una gramática limpia? ¿Está bien formada? En caso de que no lo sea, encontrar otra gramática equivalente bien formada. b) Encontrar el analizador sintáctico LL más simple que reconozca el lenguaje generado por dicha gramática.

2.55. Dado el alfabeto Σ={x,y,z}, se considera el lenguaje L = {xm yn zt / m = 2(n + t), n,m>0, t≥0} Se pide: a) Encontrar un Autómata de Pila cuyo lenguaje sea L y que vacíe su pila antes de aceptar cualquier cadena. b) Dar el conjunto de cadenas de L de longitud inferior a 5.

2.56. Dar un analizador sintáctico del tipo LL(k) (tabla y algoritmo), con k por determinar y mínimo, para la siguiente gramática con axioma S: S := xMz | yNz | λ M := xMz | N | λ N := yNz | yz. 2.57. Determinar el analizador sintáctico más simple del tipo LL (tabla y algoritmo) que reconozca el lenguaje generado por la gramática siguiente con ΣT = {a,b,c} y ΣN = {S, A}, axioma S y las reglas 20 © Inmaculada Luengo

U.L.P.G.C.

S := Sa | aAc | c A := Ab | ba 2.58. Se considera el lenguaje L = {xnymzt / m ≥ n + t, m,n,t ≥0 } sobre el alfabeto Σ={x,y,z}. Se pide construir un Autómata de Pila cuyo lenguaje sea L y que vacíe su pila antes de aceptar cualquier cadena.

© Inmaculada Luengo

U.L.P.G.C.

21