Guia2-AutomatasFinitos2012

8/2/2019 Guia2-AutomatasFinitos2012

http://slidepdf.com/reader/full/guia2-automatasfinitos2012 1/8

Sintaxis y Semántica de Lenguajes I.S.I - UTN

Autómatas Finitos 2012

Página 1 de 8

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 a consecutivas 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 un AFD 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 unosconsecutivos}

3) Diseñe un AFD que acepte el lenguaje

L = { w | w tiene 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 conjunto de 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 de las cadenas que empiezan o terminan con 01 (o ambas cosas).





Página 2 de 8

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 todas las 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ímboloc, y si aparece la subpalabra ba 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 de

veces (posiblemente ninguna) la subcadena bc.

g) ∑ = {a, b}. las palabras que enen un número par de símbolos a y no conenen 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) bab

b) aaba

c) aaaaaab

d) babababab

8) Obtener el AFN que acepte las cadenas del alfabeto ∑ = {a,b}

a) Que contengan al menos dos a consecutivas.

b) Que terminen con bb





Página 3 de 8

9) Dado el siguiente lenguaje L2= xx*(xy)*y.

a) Encontrar un AFN que acepte el lenguaje L2.

b) Utilizando la función de transición extendida correspondiente al AFN del punto

anterior, demostrar que la cadena xxyy es válida.

10) Convertir el siguiente AFN a AFD

0 1

p {p,q} {p}

q {r} {r}

r {s} Ф

*s {s} {s}

11) Convertir el siguiente AFN a AFD0 1

p {q,s} {q}

*q {r} {q,r}

r {s} {p}

*s Ф {p}

12) Convertir el siguiente AFN a AFD y describir informalmente el lenguaje que acepta.

0 1

p {p,q} {p}

q {r,s} {t}

r {p,r} {t}

*s Ф ф

*t Ф ф

13) Dado los siguientes AFN, obtener los AFD equivalentes en cada caso:

a.





Página 4 de 8

b.

14) Dados los lenguajes L(A1), L(A2) y L(A3) representados por los AFD A1, A2 y A3 mostrados

a continuación, comprobar que tales lenguajes son equivalentes.

(A1)

(A2) (A3)

15) Minimizar los siguientes AFD:

a)





Página 5 de 8

b)

c)

16) Diseñar AFN-ε para los siguientes lenguajes. Intente utilizar transiciones ε para facilitar el

diseño:

a) El conjunto de cadenas con cero o más letras a seguidas de cero o más letras b,

seguidas de cero o más letras c.

b) El conjunto de cadenas formadas por 01 repetida una o más veces, o por 010 repetida

una o más veces.

c) El conjunto de cadenas de ceros y unos con 1 al menos en una de las 3 últimas

posiciones.

17) Dado el siguiente AFN-ε:

Encontrar las clausuras-ε de cada estado





Página 6 de 8

18) Dado el siguiente AFN-ε:

q3

q1

q2

ε

b

q0

b

b

a

a

b

ε

ε

ε

c. Determinar si la cadena aab es reconocida por el AFN-ε

d. Obtener el AFD equivalente

19) Dado el siguiente AFN-ε E, aplicando el procedimiento de construcción de subconconjunto,

convertir a AFD.

E = (Q, ∑, f, p, F) donde:

Q = {p, q, r}

∑ = {a, b, c}

F = {r}

f ε a b c

p Ф {p} {q} {r}

q {p} {q} {r} ф

* r {q} {r} ф {p}

20)

a) Construya y especifique formalmente un AFN con todas sus componentes que

reconozca el lenguaje ( x |y )* xyy. Mostrar el grafo y la tabla de transiciones para el

AFN.b) Utilizando la función de transición extendida describa el proceso de la entrada xxyy.

c) Construya y especifique formalmente un AFD con todas sus componentes que

reconozca el mismo lenguaje que el AFN del item a.

d) Utilizando la función de transición extendida describa el proceso de la entrada xyxyy.

21) Construir y especificar todos los componentes de los AFDs que acepten los siguientes

lenguajes.

a) L1: formado por cadenas del alfabeto {a,b, …, z, , /, *} que permitan definir

comentarios en el lenguaje de programación C.

Siendo Letras={a,b, …, z}, Espacio el conjunto que contiene al espacio en blanco y

SimbolosEspeciales={/, *}, el alfabeto es Letras U Espacio U SimbolosEspeciales y





Página 7 de 8

L1 = /*(Letras + Espacio)* */

Por ejemplo, comentarios válidos:

/* Esto es un comentario en el lenguaje c */

/**/

Comentarios no válidos

/*/

/* Este no es un comentario valido

b) L2: formado por cadenas del alfabeto {a,b, …, z, , /} que permitan definir comentarios

en el lenguaje de programación C++.

Siendo Letras={a,b, …, z}, Espacio el conjunto que contiene al espacio en blanco y

SimbolosEspeciales={/}, el alfabeto es Letras U Espacio U SimbolosEspeciales y

L2 = // (Letras + Espacio)*

Por ejemplo, comentarios válidos:// Esto es un ejemplo de comentario

//

Comentarios no válidos:

/ Este no es un comentario valido

Este tampoco //

22) Modelizar la solución a cada uno de los siguientes problemas utilizando Autómatas Finitos

(AF’s), recordando que los estados del AF representan la memoria. Especificar las

asunciones que considere necesarias realizar:

a) Un hombre, un lobo, una oveja y un repollo están en el lado izquierdo de un río. Hay

una lancha en la cual pueden ir el hombre y uno de los otros tres. El hombre desea

cruzar al lado derecho del río y puede cruzar sólo a uno de los otros por vez. No

obstante si el hombre deja al lobo y a la oveja solos, seguramente el lobo se comerá a

la oveja. De igual modo si se quedan la oveja y el repollo solos, la oveja se comerá al

repollo. ¿Es posible cruzar el río sin que la oveja o el repollo sean comidos? Considerar

que el estado inicial del AF es aquel en el cual se encuentran los cuatro del lado

izquierdo y el estado final es aquel en el cual los cuatro están del lado derecho.

b) Las comunicaciones de redes entre procesadores independientes son gobernadas por

un protocolo, un ejemplo de ello es el Protocolo Kermit. Los AF’s son útiles para

implementar los programas de envío y recepción de datos. La implementación

simplificada de un programa para la recepción de archivos comienza en un estado de

espera por un requerimiento de transferencia de un archivo. La recepción de un

paquete de inicialización indica el comienzo de la transferencia, la cual espera por un

paquete de encabezado de archivo, que especifica el nombre del archivo a ser

transferido. Durante la transferencia se procesan una sucesión de paquetes de datos y

un paquete EOF señala la finalización de la transferencia de un archivo. Si se transfiere

una secuencia de archivos, entonces otro paquete de encabezado de archivo indica el

inicio de la transferencia del nuevo archivo. Finalmente, la transferencia está completa

cuando se recibe un paquete break y el programa de recepción vuelve al estado inicialy espera al próximo requerimiento de transferencia.





Página 8 de 8

c) La interacción básica de un cajero automático. Considere que en el inicio de la

operación la puerta del cajero esta cerrada y se debe pasar la tarjeta para que esta se

abra. Una vez que el usuario ingresa la tarjeta en el cajero se le pide una clave, si la

clave ingresada es errónea por segunda vez el cajero retiene la tarjeta. Si la clave es

correcta el usuario puede extraer dinero o salir. Cuando el usuario opta por extraer

dinero, el cajero solicita el monto y chequea si el saldo es suficiente, si el saldo no es

suficiente el usuario puede ingresar otro monto o salir. Se considera que la transacción

es exitosa cuando el usuario puede salir del cajero con su tarjeta.

Documents

Guia2-AutomatasFinitos2012