Please enable JavaScript.

Coggle requires JavaScript to display documents.

3.3 Conversión de un AFND a AFD - Coggle Diagram

- - - - No hacemos ningún comentario ya que el autómata es simple.
        Ahora vamos a añadir las cadenas (11), es decir, el siguiente autómata acepta el lenguaje
        (01+10)(11)
      - Hemos añadido sólo un arco etiquetado con 1 del estado 4 (el final) al estado 2.
      - Veamos su funcionamiento:
        como el arco empieza en el estado final, cabe la posibilidad de no usarse, es decir, lo que corresponde con el elemento
        ε de (11)*
        que el arco acabe en el estado 2 asegura que una vez se accede al arco, necesariamente tiene que haber otro 1 para poder alcanzar el estado final, es decir, este arco sirve para concatenar la palabra 11,
      - El siguiente paso es el lenguaje ((01+10)(11)0)
        
        Queremos que todas las palabras anteriores terminen con un 0 y, además, la expresión está encerrada bajo un *, por lo que tendrá que haber un arco al estado inicial de modo que exista la posibilidad de recorrer el autómata tantas veces como se desee.
        
        Está claro que el arco etiquetado con 0 tiene que comenzar en el estado 4. Nos vemos obligados a cambiar el estado final ya que, hasta ahora, no todas las palabras acaban en 0 (sólo la palabra 10). Así pues, el estado final actual será el estado inicial anterior:
      - Observaciones:
        El estado 1 es estado inicial y estado final. Esto no supone ningún problema ya que el último * incluye la posibilidad de tomar la palabra vacía ε
        
        En el siguiente paso vamos a concatenar las palabras del lenguaje (01+10)(11)*
        
        a las que ya teníamos anteriormente. Como la expresión anterior la hemos obtenido, en realidad, en el primer diagrama, será suficiente cambiar el estado final al estado 4:
      - Observaciones: si llamamos
        a=(01+10)(11)∗a=(01+10)(11)∗
        
        el lenguaje que queremos representar es
        (a0)∗a
        
        De este modo,
        si sólo se accede al estado 4 (estado final) una vez, la palabra es de la forma a
        si se accede n + 1 veces al estado 4, la palabra es de la forma
        (a0)1(a0)2...(a0)na0
        
        donde el subíndice de cada paréntesis indica el número de veces que se repite la secuencia a0.
        Por tanto, se trata de una palabra del lenguaje.
        
        Tabla de la función de transición del AFD: