Autómatas

Trabajo de Autómatas
I- Dado el AFD, determibe las siguientes cadenas
a)01100
δ(A,ℰ)=A
δ(A,0)=δ(δ(A,ℰ),0)=δ(A,0)=B
δ(A,01)=δ(δ(A,0),1)=δ(B,1)=A
δ(A,011)=δ(δ(B,01),1)=δ(A,1)=Aδ(A,0110)=δ(δ(A,011),0)=δ(A,0)=B
δ(A,01100)=δ(δ(A,0110),0)=δ(B,0)=C
La cadena 01100 no es aceptada por el AFD.

b)11101
δ(A,ℰ)=A
δ(A,1)=δ(δ(A,ℰ),1)=δ(A,1)=A
δ(A,11)=δ(δ(A,1),1)=δ(A,1)=Aδ(A,111)=δ(δ(A,11),1)=δ(A,1)=A
δ(A,1110)=δ(δ(A,111),0)=δ(A,0)=B
δ(A,11101)=δ(δ(A,1110),1)=δ(B,1)=A
La cadena 11101 es aceptada por el AFD


c)00110
δ(A,ℰ)=A
δ(A,0)=δ(δ(A,ℰ),0)=δ(A,0)=B
δ(A,00)=δ(δ(A,0),0)=δ(B,0)=Cδ(A,001)=δ(δ(A,00),1)=δ(C,1)=C
δ(A,0011)=δ(δ(A,001),1)=δ(C,1)=C
δ(A,00110)=δ(δ(A,0011),0)=δ(C,0)=C
La cadena 00110 no es aceptada por el AFD

II-DAdo el AFN, determine las siguientes cadenas
a)01101δ(A,ℰ)={A}
δ(A,0)=δ(A,0)={A,B}
δ(A,01)=δ(A,1) U δ(B,1)={A}U{B}={A,B}
δ(A,011)=δ(A,1)U δ(B,1)={A}U{B}={A,B}
δ(A,0110)=δ(A,0)U δ(B,0)={A,B}U{C}={A,B,C}
δ(A,01101)=δ(A,1)Uδ(B,1)Uδ(C,1)={A,B}U{B}U{C}={A,B,C}
La cadena 01101 no es aceptada por el AFN
b)10100
δ(A,ℰ)={A}
δ(A,1)=δ(A,1)={A}
δ(A,10)=δ(A,0)={A,B}
δ(A,101)=δ(A,1)Uδ(B,1)={A}U{B}={A,B}
δ(A,1010)=δ(A,0)Uδ(B,0)={A,B}U{C}={A,B,C}δ(A,10100)=δ(A,0)Uδ(B,0)Uδ(C,0)={A,B}U{C}U{D}={A,B,C,D}
La cadena 10100 no es aceptada por el AFN

c)11001
δ(A,ℰ)={A}
δ(A,1)=δ(A,1)={A}
δ(A,11)=δ(A,1)={A}
δ(A,110)=δ(A,0)={A,B}δ(A,1100)=δ(A,0)Uδ(B,0)={A,B}U{C}={A,B,C}
δ(A,11001)=δ(A,1)Uδ(B,1)Uδ(C,1)={A}U{B}U{C}={A,B,C}
La cadena 11001 no es aceptada por el AFN

III-Dado el AFN-ℰ, determine las siguientes cadenas
a)abbaaδ(p,ℰ)={p}=Clause(p)={p}
δ(p,a)={p}=Clause(p)={p}
δ(p,ab)=δ(p,b)={q}=Clause(q)={p,q}
δ(p,abb)=δ(p,b)Uδ(q,b)={q}u{r}=Clause(q) u Clause(r)={p,q}u{q,r}={p,q,r}
δ(p,abba)=δ(p,a)Uδ(q,a)Uδ(r,a)={p}u{q}u{r}=Clause(p) uClause(q) u Clause(r)={p}u{p,q}u{q,r}={p,q,r}

δ(p,abbaa)=δ(p,a)Uδ(q,a)Uδ(r,a)={p}u{q}u{r}=Clause(p) u Clause(q) u Clause(r)={p}u{p,q}u{q,r}={p,q,r}
La cadena abbaa es aceptada por...