Guìa de automatas finitos

Sintaxis y Semántica de Lenguajes
Autómatas Finitos

I.S.I - UTN
2012

GUÍA DE TRABAJOS PRÁCTICOS
TEMA: AUTÓMATAS FINITOS
1) Para los lenguajes dados sobre ∑ = {a,b} construir un AFD que lo acepte:
a) L = {w|w tiene un número par de a}
b) L = {w|w tiene un número impar de a}
c) L = {w|w tiene un número múltiplo de 3 de a}
d) L = {w|toda a en w está entre dos b}
e) L = {w|no hay dos aconsecutivas en w}
f) L = {w|w no contiene la subcadena aa ni bb}
g) L = {w|w contiene un número impar de a y un número par de b}
h) L = {w|w contiene un número impar de a y un número impar de b}
i) L = {w|w contiene ab ó ba como subcadena}
j) L = {w|w contiene ab y ba como subcadena}
k) L = {w|w contiene ab ó ba como subcadenas, pero no ambas}
2) Dado el alfabeto ∑ = {0,1} encontrar unAFD cuyo lenguaje aceptado sea:
a) L = {cadenas que empieza y acaban en 1}
b) L = {cadenas que acaban en 00 o bien en 11}
c) L = {cadenas con al menos dos símbolos consecutivos iguales}
d) L = {cadenas que no tengan dos símbolos consecutivos iguales}
e) L = {cadenas con al menos dos ceros y después de éstos al menos dos unos
consecutivos}
3) Diseñe un AFD que acepte el lenguaje
L = { w | wtiene un número par de ceros y unos}
Y descríbalo como:
a. Una quíntupla, con una descripción detallada de la función de transición f.
b. Un diagrama de transiciones
c. Una tabla de transiciones
d. Comprobar si la cadena 110101 pertenece al lenguaje, a través de la función de
transición extendida
4) Construya los AFD que acepten los siguientes lenguajes con el alfabeto {0,1}:
a) El conjuntode todas las cadenas terminadas en 00.
b) El conjunto de todas las cadenas con tres ceros consecutivos (no necesariamente al
final).
c) El conjunto de las cadenas con 011 como subcadena.
5) Construya los AFD que acepten los siguientes lenguajes del alfabeto {0,1}:
a) El conjunto de todas las cadenas en las que cada bloque de cinco símbolos
consecutivos contiene dos ceros.
b) El conjunto delas cadenas que empiezan o terminan con 01 (o ambas cosas).
Página 1 de 8

Sintaxis y Semántica de Lenguajes
Autómatas Finitos

I.S.I - UTN
2012

6) Construir un AFD para cada uno de los siguientes lenguajes formales:
a) Dado el alfabeto ∑ = {1,2,3} y el lenguaje L = {w | la suma de las cifras de w es múltiplo
de 4}. Por ejemplo, serían válidas 13, 31, 2222, etc.
b) Sea el lenguaje L= {w є {0,1}* | en w, la subcadena 00 aparece como mucho dos
veces}. Por ejemplo, la palabra 000 pertenece al lenguaje por tener dos subcadenas
00, pero no la palabra 0000, ya que contiene tres subcadenas 00. Otros ejemplos de
palabras válidas son: 01001001, 01000, 1011. Ejemplos de palabras NO correctas:
0100100100, 01000100, 010000.
c) Dado el alfabeto ∑ = {0,1}, sea el lenguaje de todaslas palabras que tienen un número
impar de símbolos 1, y además contienen la subcadena 01. Por ejemplo, serían válidas
las subcadenas 01, 010101, 110111. Pero no lo serían 1, ε, 011 ó 0101.
d) Dado el alfabeto ∑ = {a, b, c, d}, las palabras que pertenecen a este lenguaje cumplen
las condiciones de que si aparece la subpalabra db siempre está seguida por el símbolo
c, y si aparece la subpalabraba siempre está seguida por el símbolo d. por ejemplo, las
siguientes palabras: a, dbcb, aabccbadc.
e) ∑ = {a, b, c}. las palabras que pertenecen a este lenguaje cumplen simultáneamente
dos condiciones: tienen una longitud impar y contienen un número par de símbolos a
(se considera que 0 es un número par).
f) ∑ = {a, b, c}. pertenecen a este lenguaje las palabras que tienen un número par deveces (posiblemente ninguna) la subcadena bc.
g) ∑ = {a, b}. las palabras que Ɵenen un número par de símbolos a y no conƟenen la
subpalabra bbb ( se considera que 0 es un número par).
7) Dado el siguiente diagrama de transición, determinar las cadenas que son aceptadas o no
por el AFD.

a)
b)
c)
d)

bab
aaba
aaaaaab
babababab

8) Obtener el AFN que acepte las cadenas del...