Automatas

Clase 08: AFN, AFD y Construcción de
Thompson
Ejercicios 02 "Construcción de AFN´s con Thompson"
Prof. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom

efranco.docencia@gmail.com

1

•
•
•
•
•
•
•
•
•
•

Autómata finito
Clasificación de los autómatas finitos
Autómata finito no determinista (AFN)
Autómata finito determinista (AFD)Teorema sobre la transformación de AFN en AFD
Transformación de una expresión regular en un autómata
finito
Construcción de Thompson de un AFN a partir de una
expresión regular
Nomenclatura de Thompson
Ejemplos
Ejercicios 02 "Construcción de AFN´s con Thompson"

Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

Contenido

2• Un autómata finito es un modelo matemático de una
máquina que acepta cadenas de un lenguaje definido
sobre un alfabeto.
• Consiste en un conjunto finito de estados y un conjunto
de transiciones entre esos estados, que dependen de los
símbolos de la cadena de entrada.
• El autómata finito acepta una cadena x si la secuencia
de transiciones correspondientes a los símbolos de x
conducedesde el estado inicial a un estado final.

Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

Autómata finito

3

• La función f: E*x Q→Q, es en general no determinista. Así en
función de f, se hablará de autómatas finitos deterministas
AFD y autómatas finitos no deterministas AFN.
• Un autómata finito no determinista AFN secaracteriza por la
posibilidad de que dada una entrada e en un estado qi, se pueda pasar
a un estado qj, qk,...,qn sin saber a ciencia cierta, a cual de esos
estados pasará. Existiendo la misma probabilidad de que pase a
cualquiera de dichos estados.
• Un autómata finito determinista AFD es un caso particular de los
autómatas finitos, en el que la función de transición no presenta
ningunaambigüedad en las transiciones de estados para una entrada
dada.

Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

Clasificación de los autómatas finitos

4

• La definición de autómata finito no determinista AFN o AFN
coincide con la de autómata finito :

• Con la salvedad de que f: E*x Q→Q es no determinista, i.e. es aquel
quepresenta cero, una o más transiciones por el mismo carácter del
alfabeto.

Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

Autómatas finitos no deterministas
(AFN)

5

• Resolver:
Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

AFN Ejemplo

6

• Solución:
Teoríacomputacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

AFN Ejemplo

7

• Un autómata finito determinista AFD es un caso
particular de los autómatas finitos, en el que la
función de transición no presenta ninguna
ambigüedad en las transiciones de estados para una
entrada dada.

Teoría computacional
Clase 08: AFN, AFD y Construcción de ThompsonProf. Edgardo Adrián Franco Martínez

Autómatas finitos deterministas
(AFD)

• Un autómata finito determinista es una quíntupla
AFD=(E, Q, f, q1, F) donde la función f: E*x Q→Q es
determinista.
8

• "Para todo autómata finito no determinista
AFN=(E, Q, f, q1,F) se puede construir un autómata
finito determinista AFD=(E, Q’, f’, q’1, F’) tal que el
lenguaje reconocido por el autómatafinito
determinista AFD coincida con el lenguaje
reconocido por el autómata finito no determinista
AFN, es decir L(AFD) = L(AFN)".

Teoría computacional
Clase 08: AFN, AFD y Construcción de Thompson
Prof. Edgardo Adrián Franco Martínez

Teorema sobre la transformación de
AFN en AFD

9

AFN

Expresión: ab|ac*
INICIO

a

a

2

1

b
3

Teoría computacional
Clase 08:...