Agua

Procesadores de lenguaje Ejercicios del Tema 2
Ejercicio 2.1 Sean L = {a, aa, b} y M = {ab, b }. Describe LM y M3 por enumercaión Solución: LM = { aab, ab, aaab, bab, bb } M3 = { ababab, ababb, abbab, abbb, babab, babb, bbab, bbb } Ejercicio 2.2 Supongamos un lenguaje cuyos comentarios comiencen por >. Escribe la expresión regular correspondiente a estos comentarios. Solución: La primeraelección podría ser >, pero esto acepta cadenas como > a >>. Solución correcta: ] | > [^>])* >> Solución correcta: ? [^>])* >> Ejercicio 2.3 Escribir la expresión regular de un número entero que no acepte que el primer dígito sea cero salvo el número ‘0’. Solución: 0 | [1-9][0-9]* Ejercicio 2.4 Escribir una expresión regular para el conjunto de palabras reservaadas integer, real y char, para un lenguajeque acepte letras mayúsculas y minúsculas. Solución: ( (i|I)(n|N)(t|T)(e|E)(g|G)(e|E)(r|R) | (r|R)(e|E)(a|A)(l|L) | (c|C)(h|H)(a|A)(r|R) ) ( [iI][nN][tT][eE][gG][eE][rR] | [rR][eE][aA][lL] | [cC][hH][aA][rR] ) Ejercicio 2.5 ¿Cuáles de las siguientes expresiones regulares para los comentarios de C son correctas? Da un contraejemplo para las erróneas. a) / \* .* \*/

1

Procesadores de Lenguajesb) / \* [^*/]* \*/ c) / \* ([^*] | \* [^/])* \* / d) / \* ([^*]* \* + [^*/])* [^*]* \*+ / e) / \* (\** [^*/] | /)* \*+ / Solución: a) incorrecta. Acepta algo como /* comentario */ sigue */ b) incorrecta: No acepta algo como /* comentario * sigue */ c) incorrecta: No acepta algo como /* comentario **/ d) correcta: ([^*]* \* + [^*/])* representa cualquier cadena sin * que termine *[^*/]. e)correcta: Ejercicio 2.6 Escribir una expresión regular para el comentario de una línea de C++. Solución: // [^\n]* \n Ejercicio 2.7 Diseña expresiones regulares para los siguientes lenguajes:

2

a) Cualquier secuencia de caracteres encerrada entre llaves que no contenga ni el carácter | ni la llave cerrada. b) Cualquier secuencia de caracteres encerrada entre llaves que no contenga la llave cerradani el carcater | salvo que vaya precedido de la barra invertida (\|). c) Las direcciones IP en formato numérico (por ejemplo, 127.0.0.1). Solución: a) { [^|}]* } b) { ( [^|}] | \\ \| )* } c) ([0-9] | [0-9][0-9] | [01][0-9][0-9] | 2[0-4][0-9] | 25[0-5] ). ([0-9] | [0-9][0-9] | [01][0-9][0-9] | 2[0-4][0-9] | 25[0-5] ). ([0-9] | [0-9][0-9] | [01][0-9][0-9] | 2[0-4][0-9] | 25[0-5] ). ([0-9] |[0-9][0-9] | [01][0-9][0-9] | 2[0-4][0-9] | 25[0-5] ) Ejercicio 2.8 ¿Qué lenguajes representan las siguientes expresiones regulares? a) 0 (0|1)* 0 b) (0|1)* 0 (0|1) (0|1)

Ciencias de la Computación e Inteligencia Artificial

2004-2005

Procesadores de Lenguajes c) 0* 1 0* 1 0* 1 0* d) (00|11)* ( (01|10)(00|11)* (01|10)(00|11)* )* Solución: a) binarios que empiecen y terminen en 0 b) binarios de almenos 3 dígitos cuyo tercer último dígito sea un 0. c) binarios con tres dígitos 1.

3

d) cadenas de un número par de dígitos binarios. Si los transformamos en dígitos 0, 1, 2 y 3, representa las cadenas con un número por de 1s o 2s. Cadenas con un número poar de 0s y 1s. Ejercicio 2.9 Escribe expresiones regulares para los siguientes lenguajes: a) Todas las cadenas de letras que contenganlas cinco vocales en orden (las vocales pueden repetirse. b) Todas las cadenas de letras que estén en orden lexicográfico ascendente. c) Comentarios que consisten en una cadena encerrada entre /* y */, sin ningún */ intermedio salvo que aparezca entre comillas. d) Todas las cadenas de dígitos sin ningún dígito repetido e) Todas las cadenas de dígitos con a lo sumo un dígito repetido f) Todas lascadenas de 0 y 1 con un número par de 0s e impar de 1s. g) Todas las cadenas de 0 y 1 que no contienen la subcadena 011. Solución: a) [a-df-hj-np-tv-z]* [b-hj-np-tv-z]* [b-df-np-tv-z]* [b-df-hj-tv-z]* [b-df-hj-np-z]* b) [aA]*[bB]*[cC]* .... [zZ]* c) / \* ([^*] | “*/” | \* [^/] )* \*+/ d) Es posible aunque complicadísimo. Solución errónea: [0-9]* --- puede aceptar duplicados Solución inicial:...