Teoría de autómatas y lenguajes formales

Ortografía

Esta página o sección necesita una revisión de ortografía y gramática.
Puedes ayudar editándolo

CIENCIA DE LA COMPUTACIÓN (Área de Grado)

VISIÓN DE LOS AUTÓMATAS CON SALIDAS

Autómata finito determinista

En la teoría de la computación, un autómata finito determinista (AFD), es una máquina de estados finitos que acepta y rechaza cadenas de símbolos y solo produce un cálculo único (o ejecución) del autómata para cada cadena de entrada.

Definición formal

Formalmente, se define como una 5-tupla (Q, Σ, q₀, δ, F) donde:

Q es un conjunto de estados;
Σ es un alfabeto;
q₀ es el estado inicial;
δ es una función de transición;
F es un conjunto de estados finales o de aceptación.

En un AFD no pueden darse ninguno de estos dos casos:

Que existan dos transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

Procesamiento de las cadenas de un AFD

Sea A AFD y w = a1a2 −−− an una cadena de entrada para A.

Iniciamos con A en su estado q0, δ(q0, a1) = q1.

Procesamos a2, δ(q1, a2) = q2 y continuamos encontrando q3, q4, . . . , qn. δ(qi1, ai) = qi para cada i.

Si qn 2 F diremos que la entrada w = a1a2 −−− an es aceptada sino es rechazada

Ejemplo

El siguiente ejemplo es de un DFA M , con un alfabeto binario, que requiere que la entrada contenga un número par de 0.

M = ( Q , Σ, δ, q ₀ , F ) donde

· Q = { S ₁ , S ₂ },

· Σ = {0, 1},

· q ₀ = S ₁ ,

· F = { S ₁ }, y

· δ se define mediante la siguiente tabla de transición de estado :

	0	1
S ₁	S ₂	S ₁
S ₂	S ₁	S ₂

El estado S ₁ representa que ha habido un número par de 0 en la entrada hasta el momento, mientras que S ₂ significa un número impar. Un 1 en la entrada no cambia el estado del autómata. Cuando la entrada finaliza, el estado mostrará si la entrada contiene un número par de 0s o no. Si la entrada contiene un número par de 0, M terminará en el estado S ₁, un estado de aceptación, por lo que se aceptará la cadena de entrada.

El lenguaje reconocido por M es el lenguaje regular dado por la expresión regular ((1 *) 0 (1 *) 0 (1 *)) *, donde "*" es la estrella de Kleene , por ejemplo, 1 * indica cualquier número (posiblemente cero) de los consecutivos

Autómata finito no determinista

Un autómata finito no determinista (abreviado AFND) es un autómata finitoque, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquiera de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados

Función de transición extendida

Un AFND define un lenguaje: el conjunto de todas las cadenas que dan lugar a una secuencia de transiciones desde el estado inicial hasta un estado de aceptación. En términos del diagrama de transiciones, el lenguaje de un AFD es el conjunto de etiquetas ubicadas a lo largo de todos los caminos que van desde el estado inicial hasta cualquier estado de aceptación.

En la función de transición extendida se describe lo que ocurre cuando se parte de cualquier estado y se sigue cualquier secuencia de entradas.

Si d es la función de transición, entonces la función de trancisición extendida construida a partir d sera d sera.

La función de transición extendida es una función que toma un estado q y una cadena w y devuelve un estado p.

d (q,E)=q Es decir, si nos encontramos en el estado q y no leemos ninguna entrada, entonces permaneceremos en el estado q.

Supongamos que w es una cadena de la forma xa; es decir, a es el último símbolo de w y x es la cadena formada por todos los símbolos excepto el último.

Por ejemplo: w=1101 se divide en x=110 y a = 1.

Luego para calcular d (q,w), en primer lugar se calcula d (q,x), el estado en el que el autómata se encuentra después de procesar todos los símbolos excepto el ùltimo de la cadena w.

d (q,w)= d(d (q,x),a)

Lenguaje de un AFN

Un lenguaje en AFN acepta una cadena w si es posible elegir cualquier secuencia de opciones

del estado siguiente, a medida que se leen los caracteres de w, y se pasa del estado inicial a cualquier estado

de aceptación. El hecho de que otras opciones que empleen los símbolos de entrada de w lleven a un estado de

no aceptación, o no lleven a ningún estado en absoluto (es decir, la secuencia de estados “muertos”), no impide

que w sea aceptada por el AFN como un todo. Formalmente, si A = (Q, S,d ,q0,F) es un AFN, entonces,

L(A) = {w |_ ä (q0,w) ∩ F _= /0}

Es decir, L(A) es el conjunto de cadenas w pertenecientes a Σ∗ tal que δ (q0,w) contiene al menos un estado de aceptación.

Equivalencia de autómatas finitos determinista y no determinista

Toda expresión regular (que define a su vez un lenguaje regular) puede ser expresada como un autómata finito determinista, y viceversa. Dada una expresión regular, es posible construir un AFND-ε que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson. Luego, todo AFND-ε puede transformarse en un AFND equivalente, así como todo AFND puede transformarse en un AFD equivalente, mediante el método llamado construcción de conjunto potencia. Así, por transitividad, para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa.

Conversión de un AFND-ε a un AFND

La conversión de un AFND-ε en un AFND se basa en el concepto de clausura-ε, que corresponde a una clausura transitivacontextualizada en la teoría de autómatas.

Dado un estado q, se llama clausura-ε(q) al conjunto de todos los estados a los que se puede acceder a partir de q, procesándose a lo más un único símbolo de la entrada. Puede definirse recursivamente de la siguiente manera:

(Base inductiva) Para todo estado q, q ∈ clausura-ε(q).
(Inducción) Dados dos estados p y r, si p ∈ clausura-ε(q) y r ∈ δ(p,ε), entonces r ∈ clausura-ε(q).

El algoritmo para eliminar las transiciones vacías es el siguiente:

Se calcula la clausura-ε del estado inicial, formándose un conjunto A que corresponderá al estado inicial del nuevo autómata.
Para cada símbolo del alfabeto, se verifican los estados alcanzables a partir de algún estado contenido en A, y se calcula la clausura-ε de dichos estados alcanzables. Si dichas clausuras producen nuevos conjuntos distintos de A, estos serán nuevos estados a los que se accederá a partir de A y del símbolo correspondiente.
Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.

VISIÓN DE LAS EXPRESIONES REGULARES Y LENGUAJE REGULARES

Expresiones regulares

Una expresión regular , regex o regexp (a veces llamada expresión racional ) , en la teoría informática y teoría del lenguaje formal, una secuencia de caracteres que definen un patrón de búsqueda. Por lo general, este patrón es utilizado por algoritmos de búsqueda de cadenas para operaciones de "búsqueda" o "búsqueda y reemplazo" en cadenas .

El concepto surgió en la década de 1950 cuando el matemático estadounidense Stephen Cole Kleene formalizó la descripción de un lenguaje regular . El concepto entró en uso común con las utilidades de procesamiento de texto de Unix . Desde la década de 1980, existen diferentes sintaxis para escribir expresiones regulares, una es el estándar POSIX y otra, ampliamente utilizada, es la sintaxis de Perl.

Las expresiones regulares se usan en los motores de búsqueda , los diálogos de búsqueda y reemplazo de procesadores de texto y editores de texto , en utilidades de procesamiento de texto como sed y AWK y en el análisis léxico . Muchos lenguajes de programación proporcionan capacidades regex, integradas o vía librerías.

Operadores de las expresiones regulares

Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular 01∗ +10∗ define el lenguaje que consta de todas las cadenas que comienzan con un 0 seguido de cualquier número de 1s o que comienzan por un 1 seguido de cualquier número de 0s. No esperamos que el lector sepa ya cómo interpretar las expresiones regulares, por lo que por el momento tendrá que aceptar como un acto de fe nuestra afirmación acerca del lenguaje de esta expresión. Enseguida definiremos todos los símbolos empleados en esta expresión, de modo que pueda ver por qué nuestra interpretación de esta expresión regular es la correcta. Antes de describir la notación de las expresiones regulares, tenemos que estudiar las tres operaciones sobre los lenguajes que representan los operadores de las expresiones regulares. Estas operaciones son:

1. La unión de dos lenguajes L y M, designada como L ∪ M, es el conjunto de cadenas que pertenecen a L, a M o a ambos. Por ejemplo, si L = {001,10,111} y M = {ε ,001}, entonces L ∪ M = {ε ,10,001,111}.

2. La concatenaciónde los lenguajes L yM es el conjunto de cadenas que se puede formar tomando cualquier cadena de L y concatenándola con cualquier cadena de M. Recuerde la Sección 1.5.2, donde definimos la concatenación de una pareja de cadenas; el resultado de la concatenación es una cadena seguida de la otra. Para designar la concatenación de lenguajes se emplea el punto o ningún operador en absoluto, aunque el operador de concatenación frecuentemente se llama “punto”. Por ejemplo, si L={001,10,111} y M = {ε ,001}, entonces L.M, o simplemente LM, es {001,10,111,001001,10001,111001}. Las tres primeras cadenas de LM son las cadenas de L concatenadas con ε . Puesto que ε es el elemento identidad para la concatenación, las cadenas resultantes son las mismas cadenas de L. Sin embargo, las tres últimas cadenas de LM se forman tomando cada una de las cadenas de L y concatenándolas con la segunda cadena de M, que es 001. Por ejemplo, la concatenación de la cadena 10 de L con la cadena 001 de M nos proporciona la cadena 10001 para LM.

Construcción de una expresión regular

Específicamente, las expresiones regulares se construyen utilizando los operadores unión, concatenación y clausura de Kleene. Toda expresión regular tiene algún autómata finito asociado.

Alternación

Una barra vertical separa las alternativas. Por ejemplo, "marrón|castaño" se corresponde con marrón o castaño.

Cuantificación

Un cuantificador tras un carácter específica la frecuencia con la que éste puede ocurrir. Los cuantificadores más comunes son "?", "+" y "*":

? El signo de interrogación indica que el carácter que le precede puede aparecer como mucho una vez. Por ejemplo, "ob?scuro" se corresponde con oscuro y obscuro.

+ El signo más indica que el carácter que le precede debe aparecer al menos una vez. Por ejemplo, "ho+la" describe el conjunto infinito hola, hoola, hooola, hoooola, etcétera.

* El asterisco indica que el carácter que le precede puede aparecer cero, una, o más veces. Por ejemplo, "0*42" se corresponde con 42, 042, 0042, 00042, etcétera.

Agrupación

Los paréntesis pueden usarse para definir el ámbito y precedencia de los demás operadores. Por ejemplo, "(p|m)adre" es lo mismo que "padre|madre", y "(des)?amor" se corresponde con amor y con desamor.

Los constructores pueden combinarse libremente dentro de la misma expresión, por lo que "H(ae?|ä)ndel" equivale a "H(a|ae|ä)ndel".

La sintaxis precisa de las expresiones regulares cambia según las herramientas y aplicaciones consideradas, y se describe con más detalle a continuación.

Álgebra de las expresiones regulares

Asociatividad y conmutatividad.

Existen un conjunto de leyes algebraicas que se pueden utilizar para las expresiones regulares:

Ley conmutativa para la unión: L+M = M+L:

Ley asociativa para la unión (L+M) + N: L+ (M+N)

Ley asociativa para la concatenación: (LM)N = L(MN)

Elemento identidad y Elemento nulo.

Una identidad para un operador es un valor tal que cuando el operador se aplica a la identidad y a algún otro valor, el resultado es el otro valor.

0 es la identidad para la adición: 0 + x = x + 0 = x.
1 es la identidad para la multiplicación: 1 × x = x × 1 = x
∅ es la identidad para la unión: ∅ + L = L + ∅= L
𝜖 es la identidad para la concatenación: 𝜖L= L 𝜖 = L
∅ es el identidad para la concatenación: ∅L= L∅ = ∅

Leyes distributivas.

Como la concatenación no es conmutativa, tenemos dos formas de la ley distributiva para la concatenación:

Ley Distributiva Izquierda para la concatenación sobre unión: L(M + N) = LM + LN
Ley Distributiva Derecha para la concatenación sobre unión: (M + N)L = ML + NL

Leyes de idempotencia.

Se dice que un operador es idempotente (idempotent) si el resultado de aplicarlo a dos argumentos con el mismo valor es el mismo valor

la suma no es un operador idempotente: x + x ≠ x (aunque para algunos valores si aplica como 0 + 0 = 0)

En general la multiplicación tampoco es idempotente: x × x ≠ x
La unióne intersección son ejemplos comunes de operadores idempotentes
. Ley idempotente para la unión: L + L = L

Propiedades de clausura de los lenguajes regulares

muchas operaciones entre lenguajes que conservan a los lenguajes regulares, en el sentido que la operación aplicada produce un lenguaje regular. Si una clase de lenguajes es cerrada bajo una cierta operación, ese hecho es llamado una propiedad de clausura

La unión de dos lenguajes regulares es regular. Los regulares son cerrados por la operación de unión.
La concatenación de dos lenguajes regulares es regular. Los regulares son cerrados por la operación de concatenación.
La estrella de Kleene de un lenguaje regular es regular. Los regulares son cerrados por la operacion de estrella de Kleene.

Otras propiedades de clausura de los regulares

El complementario de un lenguaje regular es regular. Los regulares son cerrados por la operaci´on de complemento.
El reverso de un lenguaje regular es regular. Los regulares son cerrados por la operaci´on de reverso.
La intersección de dos lenguajes regulares es regular. Los regulares son cerrados por la operación de intersección.

Clausura de lenguajes regulares para las operaciones booleanas

Las primeras propiedades de clausura son las tres operaciones booleanas: unión, intersección y complementación:

1. Sean L y M lenguajes del alfabeto Σ. Luego L ∪ M es el lenguaje que contiene todas las cadenas que pertenecen a L, a M o a ambos.

2. Sean L y M lenguajes del alfabeto Σ. Luego L ∩ M es el lenguaje que contiene todas las cadenas quepertenecen tanto a L como a M.

3. Sea L un lenguaje del alfabeto Σ. Entonces L, el lenguaje complementario de L, es el conjunto de las cadenas pertenecientes a Σ∗ que no pertenecen a L.

Los lenguajes regulares son cerrados para las tres operaciones booleanas. Las demostraciones aplican enfoques bastante diferentes, como veremos a continuación.

Homomorfismo

Un homomorfismo de cadenas es una función sobre cadenas que sustituye cada símbolo por una cadena determinada.

EJEMPLO

La función h definida por h(0)= ab y h(1) =ε es un homomorfismo. Dada cualquier cadena formada por ceros y unos, todos los ceros se reemplazan por la cadena ab y todos los unos se reemplazan por la cadena vacía. Por ejemplo, h aplicada a la cadena 0011 proporciona abab.

Formalmente, si h es un homomorfismo sobre el alfabeto Σ y w = a1a2 · · ·an es una cadena de símbolos perteneciente a Σ, entonces h(w) = h(a1)h(a2) · · ·h(an). Es decir, aplicamos h a cada símbolo de w y concatenamos los resulatados en orden. Por ejemplo, si h es el homomorfismo del Ejemplo 4.13 y w = 0011, entonces h(w) = h(0)h(0)h(1)h(1)= (ab)(ab)(ε )(ε) = abab

Homomorfismo inverso

Los homomorfismos también se pueden aplicar “hacia atrás” y en este modo también se conservan los lenguajes regulares.

Es decir, suponemos que h es un homomorfismo que convierte un alfabeto Σ en cadenas de otro alfabeto T (aunque posiblemente será el mismo).2 Sea L un lenguaje con el alfabeto T. Luego h−1(L), que se lee “h inverso de L”, es el conjunto de cadenas w pertenecientes a Σ∗ tales que h(w) pertenece a L.

Propiedades de decisión de los lenguajes regulares

El lenguajetípico es infinito, por lo que no es posible presentar las cadenas del mismo a alguien y plantear una pregunta que requiera inspeccionar el conjunto infinito de cadenas. En lugar de esto, presentamos un lenguaje proporcionando una de las representaciones finitas del mismo que hemos desarrollado: un AFD, un AFN, un AFN-ε -NFA o una expresión regular.

Por supuesto, el lenguaje así descrito será regular y de hecho no existe ninguna forma de representarcompletamente lenguajes arbitrarios.

Conversión entre representaciones

Sabemos que podemos convertir cualquiera de las cuatro representaciones de los lenguajes regulares en cualquiera de las otras tres representaciones. proporciona el camino para pasar de una representación a cualquiera de las otras. Aunque existen algoritmos para cualquiera de las conversiones, a veces estaremos interesados no sólo en la posibilidad de realizar una conversión, sino también en el tiempo que tardará. En concreto, es importante diferenciar entre algoritmos que tardan un tiempo que crece exponencialmente (en función del tamaño de su entrada), y que por tanto pueden implementarse sólo para instancias relativamente pequeñas, y aquellos que tardan un tiempo que es lineal, cuadrático o polinómico de grado pequeño en función del tamaño de su entrada. Estos últimos algoritmos son “realistas” en el sentido de que se espera de ellos que sean ejecutables para casos más grandes del problema.

Equivalencia y minimización de autómatas

Se dice que dos autómatas finitos son equivalentes, si ambos reconocen el mismo lenguaje regular.

Toda expresión regular (que define a su vez un lenguaje regular) puede ser expresada como un autómata finito determinista, y viceversa. Dada una expresión regular, es posible construir un AFND-ε que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson. Luego, todo AFND-ε puede transformarse en un AFND equivalente, así como todo AFND puede transformarse en un AFD equivalente, mediante el método llamado construcción de conjunto potencia. Así, por transitividad, para cualquier autómata finito no determinista siempre existe un autómata finito determinista equivalente, y viceversa. Normalmente en el diseño de autómatas finitos, lo primero que se hace es construir un AFND-ε, que es el más sencillo de construir, por poseer menos restricciones en su función de transiciones. Luego dicho autómata se reduce a un AFND, y finalmente a un AFD, el cual por sus características deterministas ya puede ser implementado sin problemas utilizando un lenguaje de programación.

Cómo comprobar la equivalencia de estados

Comenzamos planteándonos una pregunta sobre los estados de unAFD. Nuestro objetivo es comprender cuándo dos estados distintos p y q pueden reemplazarse por un único estado que se comporte como ambos. Decimos que los estados p y q son equivalentes si:

Para toda cadena de entrada w, δ (p,w) es un estado de aceptación si y sólo si δ (q,w) es un estado de aceptación.

Dicho de manera más informal, es imposible distinguir dos estados equivalentes p y q simplemente partiendo de uno de los estados y preguntando si una determinada cadena de entrada lleva o no a un estado de aceptación cuando el autómata parte de ese estado (desconocido). Observe que no requerimos que δ (p,w) y δ (q,w) sean el mismo estado, sólo que ambos sean estados de aceptación o de no aceptación.

Si los dos estados no son equivalentes, entonces decimos que son distinguibles. Es decir, el estado p es distinguible del estado q si existe al menos una cadena w tal que δ (p,w) es un estado de aceptación y δ(q,w) no, o viceversa.

Cómo comprobar la equivalencia de lenguajes regulares

El algoritmo de llenado de tabla nos proporciona una forma fácil de comprobar si dos lenguajes regulares son el mismo. Supongamos que tenemos los lenguajes L y M, cada uno de ellos representado de una manera, por ejemplo, uno mediante una expresión regular y el otro mediante un AFN. Convertimos cada una de las representaciones a un AFD. Ahora, imaginemos un AFD cuyos estados sean la unión de los estados de los AFD correspondientes a L y M. Técnicamente, este AFD tendrá dos estados iniciales, pero realmente el estado inicial es irrelevante para la cuestión de comprobar la equivalencia de estados, por lo que consideraremos uno de ellos como único estado inicial.

Ahora comprobamos si los estados iniciales de los dos AFD originales son equivalentes, utilizando el algoritmo de llenado de tabla. Si son equivalentes, entonces L = M, y si no lo son, entonces L = M.

Minimización de un AFD

Otra importante consecuencia de la comprobación de la equivalencia de estados es que podemos “minimizar” los AFD. Es decir, para cada AFD podemos encontrar otro AFD equivalente que tenga menos estados que cualquier AFD que acepte el mismo lenguaje. Además, excepto por la posibilidad de denominar a los estados con cualquier nombre que elijamos, este AFD con un número mínimo de estados es único para ese lenguaje. El

algoritmo es el siguiente:

1. En primer lugar, eliminamos cualquier estado al que no se pueda llegar desde el estado inicial.

2. A continuación, se dividen los restantes estados en bloques, de modo que todos los estados de un mismo

bloque sean equivalentes y que no haya ningún par de estados de bloques diferentes que sean equivalentes.