Scribd
Cargar
8 vistas3 páginas

Ejercicios de autómatas y lenguajes

El documento presenta una serie de ejercicios sobre autómatas y lenguajes formales, incluyendo la identificación de estados y transiciones en diferentes autómatas. Se solicita a los estudiantes que encuentren valores específicos y simplifiquen los autómatas eliminando estados no accesibles. Además, se incluyen algunas soluciones a los problemas planteados.

Cargado por

al2203029674
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
8 vistas3 páginas

Ejercicios de autómatas y lenguajes

El documento presenta una serie de ejercicios sobre autómatas y lenguajes formales, incluyendo la identificación de estados y transiciones en diferentes autómatas. Se solicita a los estudiantes que encuentren valores específicos y simplifiquen los autómatas eliminando estados no accesibles. Además, se incluyen algunas soluciones a los problemas planteados.

Cargado por

al2203029674
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Lista de ejercicios para el curso de

LENGUAJES Y AUTÓMATAS
Tarea 1
Parte 3

En los problemas 96-97 considera el autómata A = (Q, Σ, δ, A0 , F ) definido en cada tabla.


Encuentra Q, Σ, A0 y F , haz el diagrama de transiciones del autómata y halla los valores que
se piden en cada inciso.

96. a) δ(B, 0). b 1101).


c) δ(A, 97. b
a) δ(B, 10a11). b a01a01).
c) δ(A,
b) δ(C, 1). b 01001).
d ) δ(A, b
b) δ(B, aa1100). b a11a00).
d ) δ(C,

0 1 a
0 1 →A B C D
→A B C ∗B B C C
B A C ∗C A A D
∗C C A ∗D B B B

En los problemas 98-102 haz el diagrama de transiciones del autómata definido en cada tabla.
Simplifica el autómata encontrando una partición eliminando los estados que no son accesibles.

0 1 0 1
→A C E →A B C
B F E B D E
∗C A G C F G
100.
D C E ∗D D E
98. ∗E I B E F G
∗F D H ∗F E D
G F I ∗G F G
H C J
I J E
J I E

0 1 2
→A C E B
B D E B
99. C A D F
∗D F B C
∗E F B A
∗F D B C

1
0 1 0 1
→A D K →A B C
B H K B D E
C I E C K G
D C G D H E
∗E K I E F D
101.
F B E 102. ∗F J G
∗G C I G E G
∗H C B H B K
I G K I C A
∗J F B J D G
K C F K F D
L C J

En los problemas 103-104 haz la tabla de transiciones del autómata que se muestra. Simplifica
el autómata encontrando una partición, elimina los estados que no son accesibles.

103. 104. 0
B 0
0 0 0 0
A B C D
A 1 E 1
0 1 1
1 1 1 1
1 1
0
1 C D F E
0
0 0

2
Algunas soluciones
Nota: Las soluciones de los problemas que piden dar una cantidad de elementos de un conjunto
son únicamente algunos ejemplos de varios que se pueden dar, a menos que la solución indique
que no hay más.
96.a. A. 96.c. C. 97.a. C. 97.c. C.

96.b. A. 96.d. A. 97.b. B. 97.d. B.


n o n o
98. P = {A, B, D}, {C, F }, {E}, {G, H}, {I, J} 101. P = {A}, {B, I}, {C, F }, {D}, {E}, {G, H, J}, {K} . En el
caso de {G, H, J}, puede ser igual a {G, H} si se eliminaron
los estados no alcanzables desde el principio.
n o
99. P = {A}, {B}, {C}, {D, F }, {E}

n o n o
100. P = {A}, {B}, {C, E}, {D}, {F }, {G} 102. P = {A, J}, {B, D, H}, {C, G}, {E, K}, {F }

También podría gustarte