7/24/2019 Apunte4_LFyA

1/4

Universidad Nacional Autnoma de Mxico

Asignatura:

Lenguajes formales y autmatas

Tarea:

Apunte 4

Integrantes:

- Constantino Mota Oscar Alfredo

- Quintero Ortiz Jatniel

- Tenorio Vargas Luis Erik

12 de Febrero del 2014 Mxico, D.F.

7/24/2019 Apunte4_LFyA

2/4

Como ya lo vimos, las Reglas de Thompson, nos sirven para construir, a partir de una expresin

regular, un Autmata, y como tambin ya lo mencionamos queremos llegar a un AFD (Autmata

Finito Determinstico) sin embargo esa representacin que obtenemos con esas reglas, no nos

llevan a un AFD, sino a un AFND (Autmata Finito No Determinstico), el cual no es lo que

queremos porque el tal, contiene transiciones psilon.

El siguiente ejemplo nos muestra la construccin de un AFND partiendo de una expresin regular,

utilizando las reglas de Thompson.

(a*/b+)* / (c*a)*

De esa expresin podemos ver que su alfabeto esta compuesto de dos simbolos a, b

={a,b}

Y el lenguaje, como ya vimos, tiende al infinito y con el siguiente autmata , podemos ver de

manera mas sencilla, cuales son las palabras que podemos formar, sin quebrantar las reglas

marcadas por la expresin regular indicada.

Como vimos, la transiciones psilon () no nos son utiles para tener un AFD, as que tenemos que

eliminarlas, a continuacin veremos los pasos a seguir para eliminarlas de nuestro grafo.

7/24/2019 Apunte4_LFyA

3/4

Eliminacin de transiciones psilon ()

Al eliminar estas transiciones, probablemente se incremente el nmero de estados iniciales y

finales, dependiendo de nuestra expresin regular, y al incrementarse este nmero de estados,

significa que an no obtenemos un AFD, para ello tenemos que realizar ms pasos.

Veremos unos pequeos ejemplos de cmo realizar esta eliminacin.

El siguiente autmata esta dado por: a+

Sin tomar en cuenta las transiciones psilon, podemos obtener las siguientes transiciones:

1a--> 33a--> 32a--> 3

Antes de eliminar estas transiciones, debemos considerar lo siguiente:

Un nodo se convierte en nodo inicial si se puede llegar hasta l, desde el nodo inicial

nicamente con transiciones psilon.

Un nodo se puede convertir en final si desde l, se puede llegar al nodo final nicamente

por transiciones psilon.

Una vez que ya hicimos las consideraciones anteriores, procedemos a eliminar, las transiciones

que no nos sirven y hacemos las transiciones que obtuvimos hace unos momentos. Y el autmata

queda de la siguiente manera:

7/24/2019 Apunte4_LFyA

4/4

Ahora vamos a considerar como quedara la representacin de la siguiente expresin: a*b

Nuevamente vamos a hacer caso omiso a las transiciones psilon y obtenemos las nuevas

transiciones:

1a--> 33a--> 33b--> 5

En la siguiente clase terminaremos la eliminacin de las transiciones psilon, del AFND que nos

quedo de la expresin (a*/b+)* / (c*a)*