Nada

UNIVERSIDAD NACIONAL





PROFESOR:


ESTEBAN BERMÚDEZ




CURSO:


ESTRUCTURAS DISCRETAS PARA INFORMÁTICA





INTEGRANTES:

UIS CARLOSADILLA MORALES1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
JEFFRY JIMENEZ CASARES

JOSEPH TELLO WONG

JOSE MANUEL MASIS MONTOYA





AÑO:

2010



1. Definaformalmente, qué es un Autómata de Pila, cómo se representa y dé un ejemplo.

1 Definición formal

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;
• [pic]
• [pic] es el estado inicial;
• [pic] es el símboloinicial de la pila;
• [pic] es un conjunto de estados de aceptación o finales.


La interpretación de [pic] con [pic] es la siguiente:

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

• Si [pic], es decir no es la palabra vacía, seavanza 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, γi) de entre los existentes en la definición de δ(s, A, Z), la función de transición del autómata.
• Se apila la cadena [pic] en la pila del autómata, quedando el símbolo A1 en la cima de la pila.
• Se cambia el control delautómata al estado pi.

Representación

Una máquina de este tipo se representa de la siguiente forma

[pic]
Al igual que un autómata finito un autómata de pila cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como el inicial y por lo menos un estado es de aceptación.
La principaldiferencia es que los autómatas de pila cuentan con una pila en donde pueden almacenar información para recuperarla más tarde.
Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la máquina, constituyen un conjunto finito que puede incluir algunos símbolos definiendo el alfabeto de la máquina y quizá algunos símbolos adicionales que se utilizan como marcas internas. Si unamaquina inserta un símbolo especial en la pila antes de efectuar algún otro calculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #.

Ejemplo
Sea el siguiente lenguaje libre del contexto[pic]; formado por las cadenas[pic]
Dicho lenguaje puede ser reconocido por el siguiente autómata con pila:
[pic]
donde lastransiciones son:
[pic]
[pic]
El significado de las transiciones puede ser explicado analizando la primera transición:
[pic]
donde [pic] es el estado actual, [pic] es el símbolo en la entrada y [pic] se extrae de la cima de la pila. Entonces, el estado del autómata cambia a [pic] y el símbolo [pic] se coloca en la cima de la pila.
La idea del funcionamiento del autómata es que al ir leyendolos diferentes símbolos a, estos pasan a la pila en forma de símbolos A. Al aparecer el primer símbolo b en la entrada, se comienza el proceso de desapilado, de forma que coincida el número de símbolos b leídos con el número de símbolos A que aparecen en la pila.









2. De una pequeña Biografía de Noam Chomsky, de Kurt Gödel y de Alan Turing.


Noam Chomsky

Noam Chomskynació el 7 de diciembre de 1928 en Filadelfia (Pensilvania), hijo del doctor William (Zev) Chomsky (estudioso de la lengua Hebrea y uno de sus más distinguidos gramáticos) y de Elsie Simonofsky, maestra de hebreo.
Ambos eran inmigrantes judío-ucranianos. Estudió filosofía, lingüística y matemática en la Universidad de Pensilvania desde 1945. Allí estuvo bajo la tutela del profesor Zellig Harris...