Taller

Trabajo Compiladores

Corporación Universitaria Remington

Trabajo Compiladores


Bogota DC, 01 De Noviembre de 2013

Trabajo Compiladores

TEORÍA DE AUTÓMATAS FINITOS

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas
abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está
estrechamente relacionada conla teoría del lenguaje formal ya que los autómatas son clasificados
a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en
inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie
de estados de acuerdo a una función de transición (que puede serexpresada como una tabla). En
la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado
cambiar dados unos determinados estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta
como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata;
la cabeza se mueve a lo largo dela cinta, leyendo un símbolo a la vez) una vez la entrada se ha
agotado, el autómata se detiene.
Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado
la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el
estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por
elautómata constituyen el lenguaje aceptado por el mismo.

Autómata finito no determinista (AFND)
Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada
símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el

Trabajo Compiladores Presentado por Leonardo Bermudez
estado q0 a un estado final F etiquetado con la palabra deentrada. Si una transición no está
definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra
es rechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer
ningún símbolo. Si un estado tiene transiciones etiquetadas con , entonces el AFND puedeencontrarse en cualquier de los estados alcanzables por las transiciones , directamente o a través
de otros estados con transiciones . El conjunto de estados que pueden ser alcanzados mediante
este método desde un estado q, se denomina la clausura de q.

Extensiones a los autómatas finitos
Los lenguajes aceptados por los autómatas descritos más arriba se denominan lenguajes
regulares. Autómatas máspotentes pueden aceptar lenguajes más complejos. Algunos de estos
autómatas son:

Autómata con pila
Son máquinas idénticas a los AFD (o AFI), exceptuando el hecho de que disponen de
una memoria adicional, haciendo uso de una pila. La función de transición

ahora dependerá

también de los símbolos que se encuentren al principio de la pila. Esta función determinará como
cambia la pila encada transición. Este tipo de autómatas aceptan los lenguajes independientes del
contexto.
Autómata linealmente acotado
Se trata de una máquina de Turing limitada.
Máquina de Turing
Son las máquinas computacionales más potentes. Poseen una memoria infinita en forma de cinta,
así como un cabezal que puede leer y cambiar esta cinta, y moverse en cualquier dirección a lo
largo de la cinta.Expresiones Regulares

Trabajo Compiladores Presentado por Leonardo Bermudez
Una expresión regular, a menudo llamada también regex, es una secuencia de caracteres que
forma un patrón de búsqueda, principalmente utilizada para la búsqueda de patrones de cadenas
de caracteres u operaciones de sustituciones. Por ejemplo, el grupo formado por las
cadenas Handel, Händel y Haendel se describe...