Taller 5 Automatas

Taller 5 Autómata de Pila
Integrantes: Xiomara Santos 9-732-1964
Iván Guerra 2-720-661
Ildefonso Gonzáles 9-731-392

1. Gramáticas:
L1= S→0R L2= S→IR|0Q11R L3= S→0RI|εR→0R|0R1|ε R→IR|ε R→ε0R0R1
Q→0Q1|ε

L4= S→0Q1R|ε L5= S→AB
Q→0Q1|ε A→0SS10|ε
R→IR|ε B→0B|S1|1

2. Sea el AP dado por:
Q={q1,q2}
∑= {a,b}
T= {a,b,z}
S=q1
Z=Z
F={q2}
Las reglas detransición dados por:
Δ(q1,ɛ,Z)= {(q2,Z)}
Δ(q1,a,Z)= {(q1,AZ)}
Δ(q1,b,Z)= {(q1,BZ)}
Δ(q1,a,A)= {(q1,AA)}
Δ(q1,b,A)= {(q1,ɛ)}
Δ(q1,a,B)= {(q1,ɛ)}
Δ(q1,b,B)= {(q1,BB)}
Realice los movimientospara procesar:
W1=abaababb; W2=abaa
* ¿Se aceptan las cadenas?
* Realiza el grafo del AP

Solución:
W1= abaababb(q1,abaababb,Z)˫(q1,baababb,aZ)˫(q1,aababb,Z)˫(q1,ababb,aZ)˫(q1,babb,aaZ)˫(q1,abb,aZ)˫(q1,bb,aaZ)˫(q1,b,aZ)˫(q1,ɛ,Z)˫(q2,Z)
Se Acepta

W2= abaa
(q1,abaa,Z)˫(q1,baa,aZ)˫(q1,aa,Z)˫(q1,a,aZ)˫(q1,ɛ,aaZ)
No se Acepta

Grafo:

3. Describa el proceso que realiza el APsiguiente sobre las cadenas: w1=c, w2=abcba, w3=abcab.
El autómata es:
Q={q1, q2, q3}
∑={a, b}
T={a, b, Z}
S=q1
Z=Z
F={q3}

Δ(q1, a, Z)=(q1, aZ)
Δ(q1, a, a)=(q1, aa)
Δ(q1, a, b)=(q1, ab)
Δ(q1,b, Z)=(q1, bZ)
Δ(q1, b, a)=(q1, ba)
Δ(q1, b, b)=(q1, bb)
Δ(q1, c, Z)=(q2, Z)
Δ(q1, c, a)=(q2, a)
Δ(q1, c, b)=(q2, b)
Δ(q2, a, a)=(q2, ε)
Δ(q2, b, b)=(q2, ε)
Δ(q2, ε, Z)=(q3, Z)
Escriba laGIC que genera las cadenas.
Muestre el grafo.

Solución:
W1= c
(q1,c,Z)˫(q2,ε,Z) ˫(q3,Z) Se acepta

W2= abcba
(q1,abcba,Z)˫(q1,bcba,aZ)˫(q1,cba,baZ)˫(q2,ba,baZ)˫(q2,a,aZ)˫(q2,ɛ,Z)˫(q3,Z)Se acepta

W3= abcab
(q1,abcab,Z)˫(q1,bcab,aZ)˫(q1,cab,baZ)˫(q1,ab,baZ)˫(q1,b,abaZ)˫(q1,ɛ,babaZ) No se acepta

L={wcw2|w є{a,b}*}

Grafo:
b,B:bBb,A:bA
b,Z:bZ
a,Z: aZ c,B:B
a,B:aB c,A:A b,B:ε...