1 k 1 r k k 1 j Entonces r k+1 1, j define al conjunto de todas las cadenas que envían A de s i a sj sin que A pase por los estados sm con m k 1 y ...

1 k 1 r k k 1 j Entonces r k+1 1, j define al conjunto de todas las cadenas que envían A de s i a sj sin que A pase por los estados sm con m k 1 y entonces r k+1 1, j define a Lk+1 1, j [que era lo que se quería demostrar]. Para completar la demostração, sean Sj1, Sj2,…, Sjk los estados aceptables de A. Como L(A) es la unión de todos los Ln 1, j en donde sj es un estado aceptable, entonces tenemos L(A) = L ( rn 1, j1 ) ∪ L ( rn 1, j2 ∪ · · · ∪ L ( rn 1, jn ) = L ( rn 1, j1 |rn 1, j2 | · · · |rn 1, jn ) Así, si hacemos r = rn 1, j1 ∣ ∣ ∣rn 1, j2 ∣ ∣ ∣ · · · ∣ ∣ ∣rn 1, jn , d l i , tenemos que L (A) L (r). En otras palabras, hemos construido una expresión regular r que define el lenguaje aceptado por A. Teorema de Kleene, Parte 2 Dado cualquier lenguaje definido por una expresión regular, existe un autómata de estado-finito que acepta el mismo lenguaje. La manera más común de demostrar la parte 2 del teorema de Kleene consiste en introducir una nueva categoría de autómatas, llamados autómatas de estado-finito no-deterministas. Son similares a los autómatas de estado-finito (deterministas) que hemos analizado, excepto que para cualquier estado y símbolo de entrada dados, el siguiente estado es un subconjunto del conjunto de estados del autómata, que podría ser el conjunto vacío. Así el siguiente estado del autómata no está unívocamente determinado por la combinación de un estado presente y un símbolo de entrada. Una cadena es aceptada por un autómata de estado-finito no-determinista si y sólo si, cuando los símbolos en la cadena se introducen en sucesión al autómata, a partir de un estado inicial, existe alguna sucesión de estados próximos a través de los cuales el autómata podría viajar para enviarlo a un estado aceptable. Por ejemplo, el diagrama de transición a la izquierda es un ejemplo de un autómata de estado-finito no- determinista muy simple que acepta al conjunto de todas las cadenas empezando con un 1. Observe que N(s0, 1) {s1, s2} y N(s0, 0) . por la definición recursiva para el lenguaje definido por una expresión regular. 1 0 1 1 s1 s2 s0 804 Capítulo 12 Expresiones regulares y autómatas de estado-finito Dado un lenguaje definido por cualquier expresión regular, existe un algoritmo recursivo rutinario para encontrar un autómata de estado-finito no-determinista que define el mismo lenguaje. La demostración del teorema de Kleene queda completa al demostrar que para cualquier autómata de estado-finito no-determinista de este tipo, existe un autómata de estado-finito (determinista) que define el mismo lenguaje. Los detalles de la demostración se dejan para un curso en teoría de autómatas. Lenguajes regulares De acuerdo al teorema de Kleene, el conjunto de lenguajes definidos por expresiones regulares es idéntico al conjunto de lenguajes aceptados por autómatas de estado-finito. Cualquiera de estos lenguajes se llama un lenguaje regular. Las breves alusiones que hicimos a lenguajes libres de contexto y a la clasificación de Chomsky sugieren que no todo lenguaje es regular. Probaremos esto dando un ejemplo de un lenguaje no-regular. Para construir el ejemplo, observe que como un autómata de estado-finito sólo puede asumir un número finito de estados y puesto que hay una cantidad infinita de sucesiones de entrada, por el principio de las casillas debe existir al menos un estado al cual el autómata retorna una y otra vez. Este es el aspecto esencial de un autómata que hace posible encontrar un lenguaje no-regular. Ejemplo 12.2.8 Demostración de que un lenguaje es no regular Sea el lenguaje L que consiste de todas las cadenas de la forma akbk, en donde k es un entero positivo. Simbólicamente, L es el lenguaje sobre el alfabeto {a, b} definido por L = {s ∈ �∗ | s = akbk , donde k es un entero positivo} Use el principio de las casillas para demostrar que L es no regular. En otras palabras, demuestre que no existe un autómata de estado-finito que acepta a L. Solución [Use una demostración por contradicción.] Suponga que no. Es decir, acepte que existe un autómata de estado-finito A que acepta a L. [Se obtendrá una contradicción.] Como A sólo tiene un número finito de estados, éstos se pueden denotar por s1, s2, s3, …, sn, en donde n es un entero positivo. Considere todas las cadenas de entrada que consisten enteramente de a: a, a2, a3, a4,…. Ahora existe una infinidad de tales cadenas y solamente una cantidad finita de estados. Así, por el principio de las casillas, deben existir un estado sm y dos cadenas de entrada a p y a q con p = q tales que cuando a p o a q sean entradas de A, éste vaya al estado sm. (Vea la figura 12.2.6.) [Las palomas son las cadenas de a, las casillas son los estados y la correspondencia asocia cada cadena con el estado al cual A va cuando se introduce la cadena.] a2 a3 ap aq a F s2 s3 sm sn s1 Cadenas de a Estados de A Hay un número infinito de esas cadenas Sólo existen n estados F(ai) = el estado al cual A va cuando se introduce ai = N*(S0, ai) Como F es uno a uno, existen cadenas ap y aq con p q tales que ambas envían A al mismo estado sm Figura 12.2.6 12.2 Autómatas de estado-finito 805 Ahora, por suposición, A acepta L. Así A acepta la cadena a p b p. Esto significa que después de que se ha introducido a p veces, entonces A se encuentra en el estado sm y de que se ha introducido p veces b se envía a A al estado aceptable sa. Pero eso implica que: a q b p también envía A al estado aceptable sa y así a q b p es aceptada por A. La razón es que después de la introducción de q veces a, A también va al estado sm y a partir de ahí, la entrada de p veces b envía A al estado sa, que es un estado aceptable. Pictóricamente, si p q, entonces a a a a a a b b se introduce p veces a se introduce p veces b se introducen adicionalmente q – p veces a sm saso Ahora, por suposición, L es el lenguaje aceptado por A. Así puesto que s es aceptado por A, entonces s L. Pero por definición de L, éste consiste sólo de cadenas con igual cantidad de a y b. Como p = q, entonces s no es elemento de L. Por tanto, s L y s no es elemento de L, lo que es una contradicción. Se tiene que la suposición es falsa y así no existe un autómata de estado-finito que acepte a L. 1. Los cinco objetos que forman un autómata de estado-finito son , , , y . 2. La tabla de siguiente estado para un autómata muestra los valores de ____ . 3. En las anotaciones de la tabla de estado siguiente, el estado inicial se indica con un y los estados aceptables están marcados por . 4. Una cadena que consiste de símbolos de entrada es aceptada por un autómata de estado-finito A si y sólo si, . 5. El lenguaje aceptado por un autómata de estado-finito A es . 6. Si N es la función de estado siguiente para un autómata de estado-finito A, la función de estado-eventual N está definida como sigue: Para cada estado s de A y para cada cadena que consiste de símbolos de entrada de A, N (s, ) . 7. Una parte del teorema de Kleene dice que dado cualquier lenguaje que es aceptado por un autómata de estado-finito, existe . 8. La segunda parte del teorema de Kleene expresa que dado cualquier lenguaje definido por una expresión regular, existe . 9. Un lenguaje regular es . 10. Dado el lenguaje que consiste de todas las cadenas de la forma a kb k , en donde k es un entero positivo, el principio de las casillas se puede emplear para demostrar que el lenguaje es . Autoexamen Conjunto de ejercicios 12.2 1. Encuentre el estado de la máquina automática del ejemplo 12.2.1, después de que se han introducido las siguientes sucesiones de monedas: a. Peseta, medio dólar, peseta b. Peseta, medio dólar, medio-dólar c. Medio dólar, peseta, peseta, peseta

1. Los cinco objetos que forman un autómata de estado-finito son , , , y .
2. La tabla de siguiente estado para un autómata muestra los valores de ____ .
3. En las anotaciones de la tabla de estado siguiente, el estado inicial se indica con un y los estados aceptables están marcados por .
4. Una cadena que consiste de símbolos de entrada es aceptada por un autómata de estado-finito A si y sólo si, .
5. El lenguaje aceptado por un autómata de estado-finito A es .
6. Si N es la función de estado siguiente para un autómata de estado-finito A, la función de estado-eventual N está definida como sigue: Para cada estado s de A y para cada cadena que consiste de símbolos de entrada de A, N (s, ) .
7. Una parte del teorema de Kleene dice que dado cualquier lenguaje que es aceptado por un autómata de estado-finito, existe .
8. La segunda parte del teorema de Kleene expresa que dado cualquier lenguaje definido por una expresión regular, existe .
9. Un lenguaje regular es .
10. Dado el lenguaje que consiste de todas las cadenas de la forma a kb k , en donde k es un entero positivo, el principio de las casillas se puede emplear para demostrar que el lenguaje es .