Introduccin

Cuando se habla de autmata, nos referimos a mquinas (abstractas o no) que sean

capaces de computar. Las mquinas de Turing son un ejemplo de un autmata tan

complejo que es capaz de resolver todos los problemas que una computadora actual

puede resolver con precisin. Sin embargo, existen autmatas ms simples que stos,

como los autmatas finitos o los autmatas de pila.

Los autmatas finitos tienen relacin con los lenguajes regulares y las expresiones

regulares, mientras que los autmatas de pila tienen relacin con los lenguajes y las

gramticas de contexto libre. Las expresiones regulares se usan en la actualidad para

la bsqueda de patrones en textos, mientras que las gramticas de contexto libre

juegan un papel escencial en la implementacin de compiladores.

Conceptos

Gramticas formales.-

Las gramticas formales son sistemas de manipulacin simblica que permiten generar

cadenas de smbolos, llamadas por estobien formadas, o bien reconocer cundo una

cadena dada est, en efecto, bien formada. En este primer captulo, meramente

introductorio, ilustraremos con varios ejemplos estos tipos de sistemas e inclusive

algunos otros sistemas un tanto ms generales.

Jerarqua de Chomski en Autmatas.-

Tipo Nombres Tipo de autmata

reconocedor

0 Irrestricta Mquinas de Turing

1 Irrestricta con

memoria limitada

Mquinas de Turing con

cinta acotada

2 Sensibles al contexto

con borro

Mquinas de Turing con

dominio total

3 Sensibles al contexto

no reductivas

Mquinas de Turing con

``espacio lineal''

4 Libres de contexto Autmatas de pila no-

deterministas

5 Libres de contexto

deterministas

Autmatas de pila

deterministas

6 Lineales Autmatas lineales

7 Regulares Autmatas regulares

Automatas.-

Los autmatas vienen a ser mecanismos formales que "realizan" derivaciones en

gramticas formales. La manera en que las realizan es mediante la nocin de

reconocimiento. Una palabra ser generada en una gramtica si y slo si la palabra

hace transitar al autmata correspondiente a sus condiciones terminales. Por esto es

que los autmatas son analizadores lxicos (llamados en INGLS "parsers") de las

gramticas a que corresponden.

Autmata finito.-

Un autmata finito (determinista) es pues una estructura de la forma

donde

Se construyen a partir de un conjunto de estados Q y de un conjunto de smbolos de

entrada T. Su funcionamiento queda determinado por una funcin de

transicin . Sit(q,s)=p esto se interpreta como que el autmata transita

del estado q al estado p cuando arriba el smbolo s. En todo autmata finito se cuenta

con un estado inicial, y un conjunto de estados finales .

Autmata no-determinista.-

Los autmatas no-deterministas se conforman como los autmatas finitos, salvo que

sus transiciones, en lugar de ser funciones, son relaciones que a cada pareja

(estado,estmulo) le asocian varios, uno o ningn estado.

Tiene una estructura de la forma donde