Page 57 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

57

cuando se llega a ellos, la secuencia de eventos que llevó hasta ahí puede considerarse como
“aceptable”.

Vista la correspondencia entre el lenguaje, el autómata y la gramática, volvamos a la definición
de autómata finito: un autómata finito no determinístico lo definimos como un modelo
matemático que contiene una quíntupla que define:

1- Un conjunto de estados.
2- Un conjunto de símbolos de entrada.
3- Una función de transición que corresponde pares estado-símbolo a conjuntos de estados.
4- Un estado que denota como el estado inicial.
5- Un conjunto de estados f que denotan los estados de aceptación o finales.
Esto es: AFD (Q, Σ, Δ, Q0, F) donde:

Q= Conjunto de estados.

Σ= Alfabeto, conjunto de símbolos de entrada de la cinta.

Δ= Función de transición que establece la forma en que transita e autómata.

Q0= Estado de inicio del autómata.

F= Conjunto de estado finales que son un subconjunto de Q (F ϵ Q)

Ejemplo:
AFD = ( Q={Q0, Q1,Q3}, Σ={1,2,3}, Δ = { (Q1,1)Q1, (Q1,2)Q1, (Q1,3)Q2, (Q2,1)Q3,
(Q2,2)Q3, (Q2,3)Q3, (Q3,1)Q3, (Q3,2)Q3, (Q3,3)Q3 }, F={Q2})

Representación gráfica:

q2
q1 3

1/2

q3

1/2/3

1/2/3

El lenguaje que genera este autómata está definido como el lenguaje sobre el alfabeto, atendiendo
a alguna propiedad que en realidad es una regla o patrón para seguir. Así las cosas, se puede