Ejercicios 1: Autómata de Pila Deben diligenciar la siguiente información: Caracterización del autómata a pila Definición formal Es un modelo mate...

Ejercicios 1: Autómata de Pila
Deben diligenciar la siguiente información:

Caracterización del autómata a pila
Definición formal
Es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce

Séptupla del autómata

???????? = (????, Σ, Γ, ????, ????, ????0, ????)

????: {????0, ????1} Conjunto finito de estados
Σ: {a, b} Alfabeto finito de entrada

Γ: {????, ????, ????}: Alfabeto de Pila ????: ???? ???? Σ ???? {ϵ} ???? Γ → 2????????????∗ Función de transición ???? (????, ????, ????) → (????, ????), {????, ????} ∈ ????, ???? ∈ Σ ???? {????}, ???? ∈ Γ y Υ ∈ Γ {ϵ}, reemplaza a X.

???? ∶ ????0 Símbolo inicial del autómata
???? ⊆ ????: ????1 Conjunto de estados finales

Transiciones
b, λ, b
a, λ, a
λ, λ, λ
a, a, λ
b, b, λ

Equivalencia entre AP por vaciado de pila y AP por estado final

Un ???????? = (????, Σ, Γ, ????, ????, ????0, ????) puede reconocer palabras del alfabeto de entrada de dos formas distintas:

Por estado final:

????????(????????) = {???? | (????0, ????, ????0) ├ ∗ (????, λ, X), (p ∈ F, X ∈ Γ∗}

Por vaciado de pila:

????????(????????) = {???? | (????0, ????, ????0) ├ ∗ (p, λ, λ), con p ∈ Q} ????????(????????) ???? ????????(????????) representan a los lenguajes reconocidos por el autómata ???????? por estado final y por vaciado de pila respectivamente.

Cuando la aceptación se realiza por vaciado de pila, el conjunto de estados finales ???? es irrelevante.

Equivalencias de ????????
Dos autómatas a pila (por vaciado de pila o por estado final), ????????1 y ????????2, son equivalentes, si aceptan el mismo leguaje, es decir, si ????(????????1) = ????(????????2)