Ejercicios Lenguajes y Automatas








Problemas de Lenguajes y Autómatas





1. Para los lengua jes dados sobre Σ = {a, b} construir una expresión regular de él y un Autómata
Finito que lo acepte:
a ) L = {w|w tiene un numero par de a′s}
b) L = {w|w tiene un numero impar de a′s}
c) L = {w|w tiene un numero múltiplo de 3 de a′s}
d ) L = {w| toda a en w está entre dos b′s}
e ) L = {w| nohay dos a′s consecutivas en w}
f ) L = {w| w no contiene la subpalabra aa ni bb}

2. Solución
a ) Una expresión regular que represente el lengua je L es b∗(ab∗ab∗)∗. El diagrama de transición de un Autómata Finito es:


b b

a



a
b) Una expresión regular para este lengua je es: b∗ab∗(ab∗ab∗)∗. El diagrama de transición de un
Autómata Finito es:


bb

a



a
c) Una expresión regular para este lengua je es: b∗(ab∗ab∗a)∗. El diagrama de transición de un
Autómata Finito es:


b b b

a a



a




d ) Una expresión regular para este lengua je es: b∗ ∪ b+(ab+ )∗ . El diagrama de transición de un
Autómata Finitoes:


b

b a

b





e ) Una expresión regular para este lengua je es: b∗(ab+ )∗ ∪ b∗a(b+ a)∗. El diagrama de transición
de un Autómata Finito es:


b

a

b





f ) Una expresión regular para este lengua je es: ǫ ∪ (b + ǫ)(ab)∗ ∪ (a + ǫ)(ba)∗. El diagrama de
transición de un Autómata Finito es:




b
b a a




1. Hallarun autómata finito que acepte el lengua je dado
a ) L = {w| w contiene un número impar de a′s y un número par de b′s}
b) L = {w| w contiene un número par de a′s y un número par de b′s}
c) L = {w| w contiene un número impar de a′s y un número impar de b′s}
d ) L = {w| w contiene un ab o ba como subpalabras}
e ) L = {w| w contiene un ab y ba como subpalabras}
f ) L = {w| wcontiene un ab ó ba como subpalabras, pero no ambas}

2. Solución

a ) Un diagrama de transición del autómata finito es:










a


a



b b b b

a



a
b) Cambiando el estado de aceptación del autómata representado arriba obtenemos el autómata:


a


a



b b b b

aa





c) De nuevo cambiando el estado de aceptación obtenemos el autómata correspondiente


a


a



b b b b

a



a





d ) A continuación un diagrama de transición de un autómata finito determinista que acepta el lengua je cuyas palabras contienen las subpalabras ab o ba o ambas







ab

b a

b a b

a

b a



e ) Este autómata acepta las palabras que contienen las subpalabras ab y ba

a b

b
a a

a, b b b

a

b a



f ) Este autómata acepta las palabras quecontienen las subpalabras ab ó ba, pero no ambas

a b

b
a a

a, b b b

a

b a






Ejercicios

1. Sean A = {0, 11} y B = {00, 01}. Hallar cada uno de estos conjuntos.

a) AB b) BAc) A2 d) B3

2. Hallar todos los pares de conjuntos de palabras A y B para los que

AB = {10, 111, 1010, 10111, 101000}



3. Describa los elementos del conjunto A∗ para los valores de A siguientes:
a) {ab} b) {aaa} c) {a, ab} d) {a, aba}

4. Determine si la palabra...