20130829120801

AUTÓMATAS FINITOS

1. Indicar el lenguaje aceptado por los siguientes autómatas :

a)

b)


c)

d)


2. Construir Autómatas Finitos que acepten los siguientes lenguajes regulares sobre Σ = {a, b}:a) Cadenas que finalicen con la subcadena ba.
b) Cadenas que contengan la subcadena “abab”.
c) Cadenas con un número de a’s múltiplo de tres.
d) Cadenas cuya longitud sea múltiplo de cuatro.
e)Cadenas en las que cada “a” está precedida y seguida de al menos una “b”.
f) Cadenas con un número par de a’s y un número impar de b‘s.
g) Cadenas que no tengan dos a’s consecutivas.
h) Cadenas quecontenga al menos dos a’s consecutivas.
i) Cadenas que contengan la subcadena “aa” o la subcadena “bb”

3. Construir Autómatas Finitos que reconozcan los siguientes lenguajes:
a) Números enteros.
b)Números Reales
c) Identificadores en Java.
d) Operadores relacionales del lenguajes Java: >,<,>=,<=,==,!=
e) Números mayores o iguales que 100 y múltiplos de 5.
f) Cadenas sobre el alfabeto {>, -, /} quecontienen al menos una flecha (“->”)

4. Construir Autómatas Finitos que acepten los lenguajes definidos por las expresiones regulares:
a) (ba)*
b) (ba | ab)*
c) (aa)*(bb)*
d) (1 | 00)*
e) (00*1)*
f)(0+(11)*)*
g) (0 | 1)(0 | 1)*00
h) ((ba)* | (ab)*)*



EJERCICIOS PROPUESTOS

5. Indicar el lenguaje aceptado por los siguientes autómatas:

a)

b)


6. Diseñar Autómatas Finitos que reconozcan lossiguientes lenguajes sobre Σ = {0, 1}:
a) Cadenas donde el nº de veces que aparece el símbolo 1 es un número impar
b) Cadenas donde el penúltimo símbolo es un 0
c) Cadenas donde el segundo componentees 0 y el cuarto es 1
d) Cadenas que cada 0 es precedido y seguido por un 1
e) Cadenas que contiene un número par de 0’s
f) Cadenas que contienen la subcadena 1010
g) Cadenas que empiecen y terminencon el mismo símbolo. Ojo con casos como 0 que empiezan y terminan con el mismo símbolo.
h) Cadenas que empiezan con 011 o terminan con 110
i) Cadenas que empiezan con 0110
j) Cadenas que no...