En referencia al diagrama de transición de A, puede ver que iniciando en s1, cuando se introduce un 1, A se envía a s2; entonces cuando se introduc...

En referencia al diagrama de transición de A, puede ver que iniciando en s1, cuando se introduce un 1, A se envía a s2; entonces cuando se introduce un 0, A retorna a s1; después de eso, cuando se introduce un 1, A se manda a s2; de ahí, cuando se introduce un 1, A se manda a s0 y finalmente, cuando se introduce un 0, A retorna a s1. Esta sucesión de transiciones de estado puede ser escrita como sigue: s1 1−→ s2 0−→ s1 1−→ s2 1−→ s0 0−→ s1. Así, después de que se han introducido en sucesión todos los símbolos de 10110, el estado eventual de A es s1, entonces N (s1, 10110) s1. Las definiciones de cadena y de lenguaje aceptados por un autómata se pueden reescribir simbólicamente empleando la función de estado-eventual. Suponga que A es un autómata de estado-finito al que se introducen un conjunto de símbolos I y la función de siguiente estado N y suponga que I es el conjunto de todas las cadenas sobre I y que es una cadena en I. es aceptada por A N (s0, ) es un estado aceptable de A. L(A) { I N (s0, ) es un estado aceptable de A} Diseño de un autómata de estado-finito Ahora consideremos el problema de iniciar con la descripción de un lenguaje y diseñar un autómata que acepte exactamente ese lenguaje. 798 Capítulo 12 Expresiones regulares y autómatas de estado-finito Ejemplo 12.2.6 Un autómata de estado-finito que acepta el conjunto de cadenas de 0 y 1 para el cual la cantidad de 1 es divisible por 3 a. Diseñe un autómata de estado-finito A que acepte el conjunto de todas las cadenas de 0 y 1 tales que la cantidad de 1’s en la cadena es divisible por 3. b. ¿Existe una expresión regular que defina a este conjunto? Solución a. Sean s0 el estado inicial de A, s1 su estado después de que se ha introducido un 1 y s2 su estado después se han introducido dos 1’s. Observe que s0 es el estado de A después de la introducción de cero 1 y como cero es divisible por 3 (0 0 3), s0 debe ser un estado aceptable. Los estados s0, s1 y s2 deben ser diferentes entre sí porque desde el estado s0 se necesitan tres 1’s para alcanzar un nuevo total divisible por 3, mientras que del estado s1 son necesarios dos 1’s y desde el estado s2 sólo se requiere un 1. Ahora el estado de A después de la introducción de tres 1’s también se puede tomar como s0 ya que después de la entrada de tres 1’s, se necesitan tres más para alcanzar un nuevo total divisible por 3. Más generalmente, si se han introducido 3k 1’s en A, donde k es cualquier entero no-negativo, entonces se necesitan tres más para que otra vez el total sea divisible por 3 (ya que 3k 3 3(k 1)). Así que el estado en el cual se han introducido 3k 1’s, para k entero arbitrario no-negativo, se puede tomar como el estado inicial s0. Por un razonamiento similar, los estados en los cuales se han introducido (3k 1) 1’s y (3k 2) 1’s, en donde k es un entero no-negativo, se pueden seleccionar como s1 y s2, respectivamente. Ahora cada entero no-negativo se puede escribir en una de las tres formas 3k, 3k 1 o 3k 2 (véase la sección 4.4), así los tres estados s0, s1 y s2 son todo lo que se requiere para crear A. Entonces los estados de A se pueden dibujar y etiquetar como se muestra a continuación. s2 s1s0 Considere las posibles entradas en A en cada uno de sus estados. No importa en qué estado se encuentre A, si se introduce un 0 entonces el número total de 1’s en la cadena de entrada permanece inalterado. Por tanto, existe un bucle con cada estado marcado 0. Ahora suponga que se introduce un 1 en A cuando éste se encuentra en el estado s0. Entonces A va al estado s1 (ya que el número total de 1’s en la cadena de entrada ha cambiado de 3k a 3k 1). Similarmente, si se introduce un 1 en A cuando éste está en el estado s1, entonces A va al estado s2 (porque el número total de 1’s en la cadena de entrada ha cambiado de 3k 1 a 3k 2). Finalmente, si se introduce un 1 en A cuando éste se encuentra en el estado s2, entonces va al estado s0 (ya que el número total de 1’s en la cadena de entrada será (3k 2) 1 3k 3 3(k 1), que es un múltiplo de 3). Se sigue que el diagrama de transición para A tiene el aspecto que se muestra a continuación. 0 1 0 11 0 Este autómata acepta el conjunto de cadenas de 0 y 1 para las cuales el número de 1 es divisible por 3. s2 s1s0 b. Una expresión regular que define al conjunto dado es 0 (0 10 10 10 ) . 12.2 Autómatas de estado-finito 799 Ejemplo 12.2.7 Un autómata de estado-finito que acepta al conjunto de todas las cadenas de 0 y 1 que contienen exactamente un 1 a. Diseñe un autómata de estado-finito A que acepte al conjunto de todas las cadenas de 0 y 1 que contienen exactamente un 1. b. ¿Existe una expresión regular que defina a este conjunto? Solución a. El autómata A debe tener al menos dos estados distintos: s0: estado inicial; s1: estado al cual A se mueve cuando la cadena de entrada contiene exactamente un 1. Si A está en el estado s0 y se introduce un 0, entonces A puede ya sea permanecer en el estado s0 (porque necesita esperar un 1 para moverse al estado s1), pero tan pronto como se introduce un 1, A se mueve al estado s1. A continuación se muestra un dibujo parcial del diagrama de transición. 0 1s0 s1 Ahora consideremos qué pasa cuando A se encuentra en el estado s1. Si se introduce un 0, entonces la cadena de entrada continúa teniendo un solo 1, así que A permanece en el estado s1. Pero si se introduce un 1, entonces la cadena de entrada contiene más de un 1, por lo que A debe dejar s1 (ya que ninguna cadena con más de un 1 es aceptada por A). No puede retornar al estado s0 porque no hay forma de ir de s0 a s1 y después de la entrada del segundo 1, A nunca puede retornar al estado s1. Por tanto, A debe ir a un tercer estado, s2, del cual no hay retorno a s1. Así ya que en s2 cada entrada puede muy bien dejar A en el estado s2. Se tiene que el diagrama de transición completo para A tiene la apariencia que se muestra a continuación. 0 0, 101 1 Este autómata acepta al conjunto de cadenas de 0 y 1, con exactamente un 1. s0 s2s1 b. Una expresión regular que define al conjunto dado es 0 10 . Simulación de un autómata de estado-finito utilizando software Suponga que se han codificado ciertos objetos con cadenas de 0 y 1. Se debe escribir un programa para controlar el procesamiento de los objetos codificados mediante cadenas que finalizan en 011; se ignoraran los objetos codificados de otra manera. Esta situación se puede modelar por el autómata de estado-finito que se muestra en la figura 12.2.5. 0 1 1 Este autómata reconoce cadenas que terminan en 011. 1 0 0 s0 s2s1 s3 Figura 12.2.5 Los símbolos del código del objeto se alimentan en sucesión en este autómata y cada cadena de símbolos en un código dado envía al autómata a uno de los cuatro estados s0, s1, s2, o s3. Si se alcanza el estado s3, el objeto se procesa; en caso contrario, el objeto se ignora. La acción de este autómata de estado-finito se puede simular con un algoritmo compu- tacional como el dado en el algoritmo 12.2.1. Algoritmo 12.2.1 Un autómata de estado-finito [Este algoritmo simula la acción del autómata de estado-finito de la figura 12.2.5, por mimetización del funcionamiento del diagrama de transición. Los estados se denotan por 0, 1, 2 y 3.] Entrada: cadena [cadena de 0 y 1 más un marcador final e] Cuerpo del algoritmo: estado : 0 símbolo : primer símbolo en la cadena de entrada while (símbolo = e) if estado 0 then if símbolo 0 then estado : 1 else estado : 0 else if estado 1 then if símbolo 0 then estado : 1 else estado :