Automata Pila

¿Determinista o no?

Construir un APP determinista para L={anbmcp | n≥0, m≥1, p=

n+m}.

10

11.2. Equivalencia de APF y APV

Teorema:

El conjunto de lenguajes aceptados por estado final por los

autómatas a pila LAPF es igual que el conjunto de lenguajes

aceptados por vaciado por pila de los autómatas a pila LAPV.

Método de demostración:

1. LAPF ⊆ LAPV

Sea AP= (Σ, Γ, Q, A0, q0, f, F) un autómata a pila y LF(AP) el

lenguaje aceptado (por estado final) de este autómata.

Construimos AP’= (Σ, Γ∪{B}, Q∪{s,r}, B, s, f’, ∅), con B∉Γ

y s,r∉Q, donde f’ esta definido por:

f’(s,λ,B)={(q0,A0B)}

f’(q,a,A)=f(q,a,A) para todo q∈Q, q∉F, a∈Σ∪{λ} y A∈Γ

f’(q,a,A)=f(q,a,A) para todo q∈F, a∈Σ y A∈Γ

f’(q,λ,A)=f(q,λ,A) ∪{(r, λ)} para todo q∈F y A∈Γ

f’(q,λ,B)= {(r, λ)} para todo q∈F

f’(r,λ,A)= {(r, λ)} para todo A∈Γ∪{B}

Se puede mostrar que LF(AP)=LV(AP’). Por tanto se verifica que

LAPF ⊆ LAPV.

11

2. LAPV ⊆ LAPF

Sea AP= (Σ, Γ, Q, A0, q0, f, F) un autómata a pila y LV(AP) el

lenguaje aceptado (por vaciado de pila) de este autómata.

Construimos AP’= (Σ, Γ∪{B}, Q∪{s,r}, B, s, f’, {r}), con B∉Γ

y s,r∉Q, donde f’ esta definido por:

f’(s,λ,B)={(q0,A0B)}f’(q,a,A)=f(q,a,A) para todo q∈Q, a∈Σ∪{λ} y A∈Γ

f’(q,λ,B)= {(r, λ)} para todo q∈Q

Se puede mostrar que LV(AP)=LF(AP’). Por tanto se verifica que

LAPV ⊆ LAPF.

De LAPF ⊆ LAPV y LAPV ⊆ LAPF se sigue que LAPV = LAPF, lo que

demuestra el teorema.

12

11.3. AP y lenguajes independientes del

contexto

Construcción de un AP a partir de una GIC

Teorema:

Sea APΣ el conjunto de todos los autómatas a pila sobre un

alfabeto Σ y LAP_Σ={L | L=L(AP) y AP∈ APΣ} la familia de

lenguajes sobre Σ aceptados por los autómatas a pila. (Da igual

si se acepta el lenguaje por estado final o por vaciado de pila.)

Sea LG_2_Σ la familia de todos los lenguajes sobre Σ generados

por gramáticas del tipo 2 (lenguajes independientes del

contexto).

⇒ LG_2_Σ = LAP_Σ .

Método de demostración:

1. LG_2_Σ⊆ LAPV_Σ

Para cada GIC, G, existe un autómata a pila por vaciado de

pila, AP, tal que L(G)=LV(AP).

⇒ Encontrar un algoritmo para construir AP a partir de una

gramática genérica G.

2. LG_2_Σ⊇ LAPV_Σ

Para cada autómata a pila, AP, por vaciado a de pila existe

una GIC, G, tal que L(G)=LV(AP).

⇒ Encontrar un algoritmo para construir G a partir de un AP

genérico.

LG_2_Σ⊆ LAPV_Σ y LG_2_Σ⊇ LAPV_Σ ⇒ LG_2_Σ=LAPV_Σ

Se verifica:

13

Lic_Σ=LG_2_Σ=LAPV_Σ=LAPF_Σ=LAP_Σ

GIC ⇒ AP reconocedor por vaciado de pila

Ejemplo:

Lenguaje L={ anbn | n≥0}:

S::=aSb|λ

⇒(bien formada) S::= aSb|ab|λ

1. Transformar gramática en FNG:

G=({a,b},{S,B},S,P)

P={S::= aSB|aB|λ, B::= b}

2. Construir autómata:

S

q

(λ,S,λ)

(a,S,SB)

(a,S,B)

(b,B,λ)

AP= ({a,b}, {S,B}, {q}, S, q, f, ∅), donde f se define por:

f(q,λ,S)={(q, λ)}

f(q,b,B)={(q,λ)}

f(q,a,S)={(q,SB),(q,B)}

(q,aabb,S) ├ (q,abb,SB)├ (q,bb,SBB)├ (q,bb,BB)├ (q,b,B)├ (q,λ,λ)

otra posibilidad: (q,aabb,S) ├ (q,abb,B) no

(q,abb,S) ├ (q,bb,SB)├ (q,bb,B)├ (q,b,λ) no

otra posibilidad:

(q,abb,S) ├ (q,abb,λ) no

(q,abb,S) ├ (q,bb,B)├ (q,b,λ) no

14

Otra posibilidad:

Gramática en FNG

G=({a,b},{S,B},S,P)

P={S::= aSB|aB|λ, B::= b}

(λ,S,aSB)

(λ,S,aB)

(λ,S,λ)

(λ,B,b)

(a,a,λ)

(b,b, λ)

S

q

AP= ({a,b}, {S,B,a,b}, {q}, S, q, f, ∅), donde f se define:

f(q,λ,S)={(q,aSB),(q,aB),(q,λ)}

f(q,λ,B)={(q,b)}

f(q,a,a)={(q,λ)}

f(q,b,b)={(q,λ)}

(q,aabb,S)├ (q,aabb,aSB)├ (q,abb,SB)├ (q,abb,aBB)├ (q,bb,BB)├

(q,bb,bB)├ (q,b,B)├ (q,b,b)├ (q,λ, λ)

(q,abb,S)├ (q,abb,aSB)├ (q,bb,SB)├ (q,bb,aBB) no

otra posibilidad:

(q,abb,S)├ (q,abb,λ) no

(q,abb,S)├ (q,abb,aB)├ (q,bb,B)├ (q,bb,b)├ (q,b,λ) no

15

Algoritmo:

Sea lagramática

...