Automatas

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

1

FACULTAD REGIONAL ROSARIO

AUTÓMATAS PUSH-DOWN Y MÁQUINAS DE TURING

GUÍA TEÓRICO-PRÁCTICA
PARA ALUMNOS DE LA CÁTEDRA
SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES
DE LA CARRERA DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN

ING. EDUARDO AMAR

PROF. ING. EDUARDO AMAR - AUTÓMATAS PUSH-DOWN Y MÁQUINAS DE TURING

SINTAXIS Y SEMÁNTICA DE LOSLENGUAJES (UTN-FRR)

2

Jerarquía de Máquinas Abstractas y Lenguajes

Comenzaremos por las gramáticas regulares o de tipo 3, que son las más simples, y
descubriremos problemas o lenguajes que exceden la capacidad de las máquinas de ese
nivel; así nos moveremos hacia niveles con lenguajes y máquinas más poderosos. En
cada nivel vamos a encontrar el mismo tipo de inconvenientes hasta llegaral nivel de las
gramáticas de tipo 0 y las máquinas de Turing.

PROF. ING. EDUARDO AMAR - AUTÓMATAS PUSH-DOWN Y MÁQUINAS DE TURING

3

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES (UTN-FRR)

1.1.1. Autómatas Push-Down
La clase de lenguajes generados por Gramáticas Libres de Contexto (GLC) es más amplia
que la clase de lenguajes definidos por Expresiones Regulares. Esto significa que todos
loslenguajes regulares pueden ser generados por GLC, como así también algunos
lenguajes no regulares (por ejemplo, {an bn} y Palíndromos).
Luego de introducir los lenguajes regulares definidos por expresiones regulares
encontramos una clase de máquinas abstractas, los Autómatas Finitos (AF) con la
siguiente propiedad dual:
•

para cada lenguaje regular hay al menos una máquina que funcionaexitosamente
solo sobre las cadenas de entrada de ese lenguaje y

•

para cada máquina en la clase, el conjunto de palabras que acepta es un lenguaje
regular.

Esta correspondencia fue crucial para nuestro profundo entendimiento de esta colección
de lenguajes.
El Pumping Lemma, complementos, intersección,
desde el punto de vista de la máquina, no desde
considerando una clase diferente delenguajes
preguntas; por lo tanto nos gustaría nuevamente
máquina.

decibilidad, fueron todos aprendidos
la expresión regular. Ahora estamos
pero queremos contestar algunas
encontrar una formulación para una

Estamos buscando un modelo matemático de alguna clase de máquinas que corresponda
análogamente a las GLC, esto es, debe haber al menos una máquina que acepta
cada GLC y ellenguaje aceptado por cada máquina es libre de contexto.
Queremos reconocedores de GLC o aceptores de GLC así como los AF son reconocedores
y aceptores de lenguajes regulares.
Esperamos que un análisis de la máquina nos ayudará a comprender los lenguajes en un
sentido más profundo, tal como un análisis de AF lleva a teoremas sobre lenguajes
regulares.
En este capítulo desarrollamos una nueva clasede máquinas. En el próximo capítulo
probamos que estas nuevas máquinas se corresponden con GLC en el sentido que
deseamos.
Para construir estas nuevas máquinas, comenzamos con nuestros viejos AF e incluimos
algunos nuevos descubrimientos que los ampliarán y los harán más potentes.
Lo que haremos primero es desarrollar una representación diferente para los AF, una que
será fácil de aumentarcon nuestros agregados.
No hemos dado hasta ahora un nombre a la parte del AF en la que reside la cadena de
entrada mientras se está ejecutando. Llamaremos a la misma la CINTA de Entrada. La
CINTA de entrada debe ser suficientemente larga para aceptar cualquier posible entrada,
y ya que cualquier palabra en a* es una posible entrada, la CINTA debe ser infinitamente
larga (tal CINTA es muycara).
La CINTA tiene una primera ubicación para la primera letra de la entrada, luego una
segunda ubicación, y así sucesivamente. Por lo tanto decimos que la CINTA es infinita en
una única dirección solamente. Algunas personas usan el término “medio infinita” para
esta condición.

PROF. ING. EDUARDO AMAR - AUTÓMATAS PUSH-DOWN Y MÁQUINAS DE TURING

4

SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES...