AUTOMATAS Y COMPILADORES EXPRESIONES REGULARES

AUTOMATAS Y COMPILADORES
EXPRESIONES REGULARES

1. Escribir 3 ejemplos de cadenas pertenecientes a los lenguajes definidos por cada una de las siguientes expresiones regulares:
a) (0|1)*00(0|1)*b) (a*|ba|b)+
c) ( 0(0|1)+1 | 1(1|0)*0 )
d) (1+(0|1)*2)+
e) x(x|y)+z | yx*y
f) (ba)*((a|b)(b|aa))+

2. Determinar en cada caso si las cadenas pertenecen al lenguaje descrito por laexpresión regular:
a) 10100010  (0*10)*
b) 011100  (0|(11)*)*
c) 000111100  ((011|11)*(00)*)*
d) 011100101  01*10*(11*0)*

3. Describir los lenguajes representados por las siguientesexpresiones regulares definidas sobre el alfabeto Σ={a,b,c}
a) (a|b)∗c
b) (aa+)(bb∗)
c) (aa+)|(bb∗)
d) a*b*c*

4. Escribir expresiones regulares que denoten los siguientes lenguajes:
a)Números naturales.
b) Números naturales que no contengan ceros innecesarios al principio: 0, 10, 121,…
c) Números pares.
d) Números impares.
e) Números reales con formato de punto fijo: 2.343,-12.0, +12.02, 0.0001, 505.00,...
f) Números reales con formato de punto flotante: -323.3e+7, 0.3E-12,...
g) Números reales con formato de punto fijo o con formato de punto flotante.

5. Escribirexpresiones regulares que definan los lenguajes definidos sobre Σ = {0, 1}:
a) Cadenas: 101, 1001, 10001, 100001,…
b) Cadenas que terminan con 110
c) Cadenas que empiezan con 011 o terminan con 110d) Cadenas que contienen la subcadena 101
e) Cadenas que contienen la subcadena 01 y la subcadena 10
f) Cadenas donde cada 0 esta precedido y seguido por un 1.
g) Cadenas que tienen una secuenciaimpar de 0s y una secuencia par de 1s
h) Cadenas que terminan con 1 y no contiene la subcadena 00
i) Cadenas que no contienen a la subcadena 01
j) Cadenas que no contienen ni la subcadena 00 ni lasubcadena 11




6. Describir los lenguajes denotados por las siguientes expresiones regulares:
a) 1*0
b) 1*00*
c) a (b|c)*a
d) a (b|c)a*
e) a*(b|c)a

7. Escribir tres cadenas de...