APORTE TRABAJO COLABORATIVO AUTOMATAS Y LENGUAJES FORMALES

APORTE TRABAJO COLABORATIVO

AUTOMATAS Y LENGUAJES FORMALES

SAUL GALINDO ROCHA

CODIGO: 72.143.625

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

UNAD

1. Describa y explique cada uno de los elementos que permiten definir formalmente un Autómata a Pila (AFPD) como una 7- upla.

R/ Un autómata con pila o autómata de pila 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. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.

Formalmente, un autómata con pila puede ser descrito como una séptupla M = (S,

Σ, Γ, δ, s, Z, F) donde:

• Σ y Γ son alfabetos de entrada, de la cadena y de la pila respectivamente;

• S un conjunto de estados

• s ε S es el estado inicial;

• Z ε Γ el símbolo inicial de la pila;

• es un conjunto de estados de aceptación o finales.

La interpretación de

es la siguiente:

Cuando el estado del autómata es s,el simbolo de la cabeza lectora esta inspeccionando en ese momento es a, y en la cima de la pila nos encontramos a el símbolo Z, se realizan las siguientes acciones:

 Si a ε Σ, es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.

 Se elimina el símbolo Z de la pila del autómata.

 Se selecciona un par (pi,yi) de entre los existentes en la defenicion de δ(s,A,Z), la función de transición del autómata.

 Se apila la cadena en la pila del automata quedando el simbolo A1 en la cima de la pila.

 Se cambia el control del autómata al estado.

5. Construir un AFPD que reconozca:

(q0,ε, Z) = (q1, Z)

(q1, x,ε) = (q1, x)

(q1, y, x) = (q2,ε)

(q2, y, x) = (q2,ε)

(q2,ε, Z) = (q3, Z)

Sea w = xxx

(q0, xxx, Z) (q1, xxx, Z) (q1, xx, xZ)

(q1, x, xxZ) (q1, ε, xxxZ)

La pila quedo llena xxxZ y el automata en el estado q1 reconcio por completo la cadena.

Sea w = xxy

(q0, xxy, Z) (q1, xxy, Z) (q1, xy, xZ)

(q1, y, xxZ) (q2,ε, xZ)

Aunque la pila no quedo del todo vacıa (quedo xZ) se reconocio toda la cadena completa y el automata quedo en un estado de aceptacion q2.

Sea w = xxyy

(q0, xxyy, Z) (q1, xxyy, Z) (q1, xyy, xZ)

(q1, yy, xxZ) (q2, y, xZ) (q2,ε, Z)

(q3,ε, Z)

La cadena es procesada por completo, en la pila queda el sımbolo inicial de pila y por tanto la cadena es aceptada.

Sea w = xyy

(q0, xyy, Z) (q1, xyy, Z) (q1, yy, xZ)

(q2, y, Z)

A pesar de que se esta en un estado de aceptacion la cadena no se termino de escanear, la transicion (q2, y, Z) no esta definida en este automata. Por tanto la cadena no es reconocida por el automata.

6. Construir un autómata con pila que reconozca por vaciado de pila el lenguaje

que contiene las palabras formadas por los símbolos “0”, “1” y “2” que tienen

tantas apariciones de las secuencia “01” como del símbolo “2”.

AP = ({0,1,2}, {Z,A}, {q0, q1, q2}, q0, Z, f,

f(q0,0,Z) = {(q1, AZ)}

f(q2, λ, Z) = {(q2, λ)}

f(q0,0,A) = { (q0,A),(q1, AA), (q2, λ)}

...