BelloEdgar_Ej15 - Edgar Bello

Vista previa del material en texto

Bello Muñoz Edgar Alejandro 2CM2 
 
Ejercicios de autómatas de pila 
Resuelva correctamente los siguientes ejercicios de autómatas de pila (AP) 
A) Sea el AP sobre el alfabeto ∑ = {a,b,c} 
a) ¿Cuál es el lenguaje aceptado por el AP? 
L = {a^n b^m a^? c a^? b^m a^n | a != b y a, b > 0 } 
b) ¿Cuál es la secuencia de estados para aceptar la cadena abacaba? 
q0 -> Z0 a -> Z0 A -> A b -> A B -> B a -> B A -> A c -> A -> A a -> λ -> B -> B b -> λ -> A -> A a 
-> q2 
c) Dibuje la tabla de transiciones de estados 
Estado Cadena Pila Agregar 
q0 -- Z -- 
q0 => q0 b A BA 
q0 => q0 b a Ba 
q0 => q0 a B AB 
q0 => q0 a b Ab 
q0 => q0 a Z aZ 
q0 => q0 b B BB 
q0 => q0 b b Bb 
q0 => q0 a A AA 
q0 => q0 a a Aa 
q0 => q0 b Z BZ 
q0 => q2 c Z Z 
q0 => q1 c B B 
q0 => q2 C A A 
q0 => q1 C b b 
q0 => q1 C a a 
q1 => q1 b B 𝜆 
q1 => q1 a A 𝜆 
q1 => q2 b b 𝜆 
q1 => q2 a a 𝜆 
 
 
 
Bello Muñoz Edgar Alejandro 2CM2 
 
B) AP que reconoce el siguiente lenguaje: 
1. {anbmcn | n,m >=1} U {cm} U { 𝜆 } 
a) Escriba 5 palabras aceptadas por el AP y 5 palabras no aceptadas por el 
AP 
Aceptada Rechazada 
abc acc 
abbc bc 
abbbc aabc 
aabcc aaaabcc 
aaabbbccc bccc 
 
b) Escriba su notación formal 
 
C) Dados los siguientes AP 
a) Escriba la séptupla de cada uno 
1. 𝑃 = { {𝑞0,𝑞1},{𝑎, 𝑏,},{𝑍0, , 𝐴, 𝐵}, 𝛽,{𝑞0},{𝑞0 }} 
2. 𝑃 = { {𝑞0,𝑞1, 𝑞2},{𝑎, 𝑏,},{𝑍0, , 𝐴, 𝐵}, 𝛽,{𝑞0},{𝑞2 } 
 
b) Determine el lenguaje aceptado por los autómatas. 
1. 𝐿 = {𝑎𝑛𝑏𝑛 |𝑛 ≥ 1 } 
2. 𝐿 = {𝑎𝑛𝑏𝑛 |𝑛 ≥ 1 } 
 
c) Dibuje el contenido de la pila en ambos AP después de haber leído la cadena 
aaabbb. 
Bello Muñoz Edgar Alejandro 2CM2 
 
1 2 
 
d) ¿Cuál es la diferencia entre el primero y el segundo? 
La principal diferencia entre ambos es que el primero se trata de un autómata 
por estado de aceptación mientras que el segundo es por pila vacía, el 
primero acepta la cadena mientras que el otro no acepta la cadena sin que 
la pila esté vacía. 
 
D) AP que reconoce el lenguaje {anbm1cn | n,m>=1} U {anbm2cm | n,m >=1} sobre 
el alfabeto ∑ = {a,b,1,2} 
a) Demuestre que las cadenas aab1cc y abbb2ccc son aceptadas por el AP. 
Bello Muñoz Edgar Alejandro 2CM2 
 
aab1cc abbb2ccc 
 
b) ¿En qué estado del autómata se queda el AP después de haber leído 
aabb11cc? 
En q3. 
c) ¿La cadena es aceptada? 
No, ya que la cadena contiene dos símbolos“1” dentro de ella, y el lenguaje 
solo puede aceptar uno.