AUTOMATAS

1. a) Ø es una ER que denota el Lenguaje…..????
-Vacio
b) λ es una ER que denota el lenguaje …?
-De palabras vacías o nulas
Para los siguientes ejercicios identifique el lenguaje que reconoce y plasme cinco posibles cadenas
válidas que representan esa ER:
si A = {a,b,c}
a) (a +b)
Reconoce el lenguaje conformado por las palabras { λ, a, b, ab} No hay ninguna otra palabra
b) (a + b ) *Reconoce el lenguaje formado por las palabras con repeticiones de a ó b ó ab
i. aaaab
ii. abababab
iii. bbbbbab
iv. aba
v. baba
c) (a+ λ )b*
Reconoce el lenguaje formado por las palabras que empiezan por a ó b y terminan en b
i. ab
ii. abbbb
iii. bbbbb
iv. ab
v. bb
d) a (ab)*
Reconoce el lenguaje de las palabras que inician en a y tienen repeticiones de ab
i. aab
ii. aabab
iii.aababab
iv. aabababab
v. aabababab
e) λ∗
Reconoce el conjunto de las palabras formadas por repeticiones de λ
i. λ
ii. λ λ
iii. λ λ λ
iv. λ λ λ λ
v. λ λ λ λ λ
si A = {0,1}
h) 000
Solo reconoce la palabra 000
i) 10* + 1
Reconoce las palabras que inician en 1 se siguen de ceros y pueden o no terminar en 1.
i. 11
ii. 10001
iii. 1000000
iv. 1000000000001
v. 1000001
j) 01* + 0
Reconocelas palabras que inician en 0 se siguen de unos y pueden o no terminar en 0.
i. 010
ii. 011110
iii. 01111111
iv. 0111111111111110
v. 0111111110
k) (1 – 110) *
El signo “-“ no esta definido en el alfabeto y no es ninguna operación con caracteres del alfabeto,
por lo tanto no tiene solución
l) (1 + 10) +
Reconoce el lenguaje formado por las palabras {λ, 1, 10, 110} no hay ninguna otrapalabra en la
expresión regular.
m) 1* 0*
Reconoce el lenguaje de las palabras que inician en 1 ó 0 y terminan en 1 ó 0
i. 10
ii. 1100
iii. 000000
iv. 1111111111100
v. 11111110000000
n) 00* 11*
Reconoce el lenguaje formado por las palabras que inician en 0 y terminan en 1
i. 0011
ii. 000011
iii. 00001111
iv. 000000001111
v. 001111111111
o) (0+1)*11(1+0)*
Reconoce el lenguaje formadopor las palabras que inician con secuencias 0 ó 1 ó 01 ó
combinaciones de las tres seguidas se 11 y terminadas en secuencias de 1 ó 0 ó 10 ó
combinaciones de las tres.
i. 0111
ii. 011110
iii. 111111
iv. 0101111010
v. 001100
2. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está
dado por la quíntupla: A = (Q, Σ, f, q, F) donde: 0
• Q es un conjunto de estados.
•Σ es el alfabeto de entrada
• f: Q X Σ → Q es la función (total) de transición.
• q0 ∈ Q es el estado inicial.
• F⊆ Q es el conjunto de estados finales.
Y que para el ejercicio, el autómata acepta las cadenas (01)* 1) :
, A = ({q0, q1, q2, q3} , {0,1} , f , qo, { q2})
Representado mediante el grafo:
EN UN SIMULADOR (YA SEA JFLAP O VAS)
a. Plásmelo en el simulador
b. Realice la tabla detransición correspondiente.
Tabla de transiciones
f 0 1
→q0 q1 q2
q1 q3 q0
# q2 q3 q3
q3 q3 q3
c. Compruebe el lenguaje aceptado.
El lenguaje aceptado es aquel comprendido por las cadenas que empiezan o no con
secuencias de 01 y terminan en 1
d. Identifique la expresión regular que permite identificar que cadenas son válidas y
que acepta el autómata.
La expresión regular que identificalas cadenas válidas y que acepta el autómata es:
𝐸𝑅 = (01)∗1
3. a. Acorde al autómata del ejercicio N 2, explique o justifique de donde proviene el
nombre “finito”. (Sea objetivo y creativo). No copie contextos puntuales de los libros o de
la web.
La palabra finito significa que su conjunto de estados es finito, es decir tiene un
determinado número de estados, también debe tener finitosnumero de estados finales.
De esta forma acepta expresiones regulares finitas.
b. Conviértalo en un AFND. Justifíquelo y explique de donde surge y por qué se da la
característica de No determinístico.
Partiendo de la definición de que un Autómata Finito No Determinístico (AFD) está
dado por la quíntupla: A = (Q, Σ, f, q, F) donde: 0
• Q es un conjunto de estados.
• Σ es el alfabeto de...