Home

LÍMITE DE LOS AUTÓMATAS FINITOS DETERMINISTAS

Esta sección tratará de distinguir entre cadenas aceptables y no aceptables por autómatas finitos deterministas.

1.3.1. Definiciones previas

     Vamos a definir |w| como la longitud de una cadena (número de símbolos que contiene el cual como se dijo antes podía ser infinito aunque contable).

     Dado un alfabeto, , vamos a considerar todas las cadenas de longitud finita (incluyendo la vacía), a partir de este alfabeto y lo vamos a designar con ^*(no confundirlo con el conjunto potencia del alfabeto, por ejemplo, en el alfabeto {a,b}, ^* será { , a, b, aa, bb, ab, ba, aaa, aab,...} y P(, a, b, ab}). Un subconjunto de ^* se llama lenguaje (varios subconjuntos denotarán distintos lenguajes).

     Si M es un autómata finito determinista (S,, , ,F), la colección de cadenas que acepta constituye un lenguaje con respecto al alfabeto ; Este lenguaje lo representamos con L(M) que se lee "el lenguaje que acepta M". L(M) es la colección de TODAS las cadenas que acepta M (ni más ni menos). El lenguaje que es aceptado por un autómata finito se llama lenguaje regular.

     Hay dos tipos especiales de lenguajes regulares:

• La colección de todas las cadenas de longitud finita de un alfabeto ( ^* )

· La colección de ninguna cadena, conocido como lenguaje vacío y se representa con  (hay que diferenciar el lenguaje con la cadena vacía { } y el lenguaje que no tiene cadenas {} El primero tiene una cadena y el segundo no tiene ninguna).

cadena vacía                                     lenguaje vacío

     Como estamos hablando de conjuntos de cadenas, podemos decir que ^* es el conjunto universal, y { } su complementario. Como los dos son lenguajes regulares, entonces podemos generalizar a cualquier lenguaje regular y su complementario, que son regulares también.

COROLARIO.- Para cualquier lenguaje regular aceptado por un autómata finito determinista L(M), existe el autómata finito determinista L(M') que acepta el lenguaje complementario con respecto al universal (L(M') = ^* - L(M)).

DEMOSTRACIÓN

Lo que se está afirmando es que para un autómata finito determinista L(M), existe el autómata finito determinista L(M') que acepta todas las cadenas que no acepta el primero. Para convertir un autómata finito en otro que acepte el lenguaje complementario se procede de la siguiente manera: Primero hay que comprobar si el diagrama esta totalmente definido; si no es así (que no aparezcan algunas transiciones), hay que convertirlo a uno que lo esté como ya se vio anteriormente. Para cada uno de los estados de L(M) que eran de aceptación, no lo serán en L(M') Para cada uno de los estados de L(M) que no eran de aceptación, en L(M') lo serán

TEOREMA.- Para cualquier alfabeto existe un lenguaje que no es igual a L(M) para cualquier autómata finito determinista M.

DEMOSTRACIÓN

Supongamos el alfabeto  que es un conjunto contable; el conjunto de todas las cadenas de longitud finita, ^*, será infinito contable (serán n N cadenas) y de aquí deducimos que la colección de autómatas finitos deterministas es infinito contable. P( ^*) es el conjunto de todos los lenguajes posibles basados en  y por lo tanto un número incontable de lenguajes distintos. Por lo tanto, siempre habrá un lenguaje que no será aceptado por una máquina de este tipo.

     Sea Wⁿ, donde W es una cadena de ^* y n es un entero no negativo. Wⁿ es la forma abreviada para representar una cadena de n copias del patrón W (si ={x,y}, entonces (xy)³=xyxyxy o y⁰= ).

1.3.2. Un lenguaje no regular

TEOREMA.- Si un lenguaje regular contiene cadenas de la forma xⁿyⁿ para enteros arbitrariamente grandes, n entonces debe contener cadenas de la forma x^myⁿ donde m y n no son iguales.

DEMOSTRACIÓN

Sea M un autómata finito determinista y supongamos que x^ny^n  L(M). Supongamos que n es lo suficientemente grande para que sea mayor que el número de estados del autómata; a este número lo llamamos k. Aceptar una cadena del tipo x^ky^k significa que, para x^k, se recorrerá más de una vez alguno de los estados antes de llegar a alguna de las y de la cadena; es decir, durante la lectura de las x se recorrerá un bucle circular del diagrama de transiciones. Si j es el número de x leídas al recorrer este bucle, entonces la máquina puede aceptar la cadena x^k+jy ^k (no podemos determinar el número de veces que repite el bucle), que no esta en L(M).

     En definitiva las cadenas de la forma xⁿyⁿ no son regulares. Un ejemplo de estos lenguajes no regulares son las expresiones matemáticas con paréntesis. Para recorrer una expresión de este tipo hay que tener en cuenta que el número de paréntesis izquierdos debe ser igual a los paréntesis derechos, de manera que habría que recordarlo, cosa que un autómata finito no puede.