• Author / Uploaded
• Consuelo Garzón

• Categories
• Modelos de computación
• Matemáticas

Citation preview

Ejercicio 1:

Realizar la conversión de AFD a AFND o de AFND a AFD según corresponda.

Gráfica 1. Autómata finito No determinista con transiciones vacías.

Este autómata es no determinista debido a que desde el estado 𝑞1 hay transiciones mediante a a dos estados diferentes 𝑞3 y 𝑞5 y tiene una transición vacía de 𝑞3 a 𝑞4 , para transformarlo en un autómata determinista primero hallamos las clausuras con respecto a λ, esto es el conjunto de estados con los que un estado va a otro a través de una transición vacía. Estas clausuras las escribimos en la siguiente tabla:

Clausura Clausura Clausura Clausura Clausura Clausura

λ(0) λ(1) λ(2) λ(3) λ(4) λ(5)

Clausura {0} U { } {1} U { } {2} U { } {3} U {4} {4} U { } {5} U { }

Tabla 1. Clausuras con respecto a λ del autómata.

Ahora realizamos la tabla de transición del autómata teniendo en cuenta las transiciones vacías (tabla 2).

𝑞0 𝑞1 𝑞2 𝑞3 𝑞4 𝑞5

λ 𝑞4 -

a 𝑞1 𝑞5 , 𝑞 3 𝑞3 𝑞5

b 𝑞2 𝑞4 𝑞0 𝑞5 -

Tabla 2. Tabla de transición del autómata.

Ayudándonos de la tabla de transición y la de clausuras, realizamos la tabla de relación de transición, la cual consiste en crear nuevos estados a partir del estado inicial, de acuerdo a las transiciones que realizan respecto al elemento del alfabeto y las transiciones vacías, los nuevos estados se van nombrando de acuerdo a como van apareciendo según las transiciones que resulten y estos mismos se evalúan posteriormente hasta que no se produzcan estados diferentes, estos se colocan con sus respectivas clausuras. Este resultado se consigna en la tabla 3. Nombramos a los nuevos estados con letras para no confundirlos con los antiguos. Los nuevos estados que posean los estados finales del autómata inicial, que en este caso son 𝑞3 , 𝑞4 y 𝑞5 , serán los nuevos estados finales o de aceptación, en este caso son los estados D,E,F y G.

A{0}U{ } B{1}U{ } C{2}U{ } D{3,5}U{4} E{4}U{ } F{3}U{4} G{5}U{ }

a B{1}U{ } D{3,5}U{ 4 } F{3}U{4} G{5}U{ } G{5}U{ }

b C{2}U{ } E{4}U{ } A{0}U{ } G{5}U{ } G{5}U{ } G{5}U{ } -

Tabla 3. Tabla de relación de transición.

Por último, realizamos una tabla de transición equivalente a la anterior, pero sólo con la etiqueta de los estados, ya que esta nos ayudará a graficar el nuevo autómata, igualmente nos damos cuenta que el autómata es determinista, ya que hay una sola transición por estado por elemento del alfabeto del autómata y no hay transiciones vacías.

A B C D E F G

a B D F G G

b C E A G G G -

Tabla 4. Tabla de transición equivalente.

Ahora graficamos nuestro nuevo autómata determinista, utilizamos la herramienta JFLAP.

Gráfica 2. Autómata finito determinista resultante.

Escribimos la tabla de transición nuevamente, pero con la nomenclatura convencional, al igual que la gráfica, para facilitar la realización de los demás ejercicios.

𝑞0 𝑞1 𝑞2 𝑞3 𝑞4 𝑞5 𝑞6

a 𝑞1 𝑞3 𝑞5 𝑞6 𝑞6

b 𝑞2 𝑞4 𝑞0 𝑞6 𝑞6 𝑞6 -

Tabla 5. Tabla de transición equivalente con nomenclatura convencional.

Gráfica 2. Autómata finito determinista resultante con nomenclatura convencional.