3.1 Conceptos: Definición y calsificación del automata finito (AF)

Conceptos: Definición y calsificación del automata finito (AF)

Los autómatas finitos son reconocedores; sólo dicen “sí” o “no” en relación con cada posible cadena de entrada.

Los autómatas finitos pueden ser de dos tipos:

Los autómatas finitos no deterministas (AFN) no tienen restricciones en cuanto a las etiquetas de sus líneas. Un símbolo puede etiquetar a varias líneas que surgen del mismo estado, y ϵ, la cadena vacía, es una posible etiqueta.

Los autómatas finitos deterministas (AFD) tienen, para cada estado, y para cada símbolo de su alfabeto de entrada, exactamente una línea con ese símbolo que sale de ese estado.

 

Tanto los autómatas finitos deterministas como los no deterministas son capaces de reconocer los mismos lenguajes. De hecho, estos lenguajes son exactamente los mismos lenguajes, conocidos como lenguajes regulares, que pueden describir las expresiones regulares.

Autómata Finito No Determinista (AFND) para una expresión regular

Intuitivamente un autómata finito consta de un conjunto de estados y, partiendo de un estado inicial, realiza transiciones de un estado a otro en respuesta a los símbolos de entrada que procesa. Cuando el autómata alcanza un estado de los que se denominan finales, se dice que ha reconocido la palabra formada por concatenación de los símbolos de entrada procesados.

Un autómata finito puede ser determinista o no determinista. La expresión «no determinista» significa que desde un mismo estado puede haber más de una transición etiquetada con el mismo símbolo de entrada.

Un autómata finito no determinista es una quíntupla (Σ, Q, δ, q0, F), donde:

Σ es un conjunto finito de símbolos de entrada o alfabeto.

Q es un conjunto finito de estados.

δ es la función de transición que recibe como argumentos un estado y un símbolo de entrada o el símbolo λ y devuelve un subconjunto de Q.

q0 ∈ Q es el estado inicial.

F ⊆ Q es el conjunto de estados finales.

Un autómata finito puede representarse mediante lo que se conoce como diagrama de transición, que es un grafo dirigido construido de la siguiente forma

Cada nodo está etiquetado con un elemento de Q.

Si δ(p,a) = q, se dibuja un arco del nodo con etiqueta p al nodo con etiqueta q etiquetado con el símbolo a.

El estado inicial aparece señalado con una flecha sin origen.

Los estados finales aparecen marcados con un doble círculo.

Figura 1.0 Diagrama de transición para un autómata.

 

El diagrama de transición para el autómata finito determinista ({0,1},{p,q,r},δ,p,{q}), de la figura 1.0, muestra δ que está definida de la siguiente forma:

 

δ(p,0)=q

δ(p,1)=r

δ(q,0)=q

δ(q,1)=r

δ(r,0)=r

δ(r,1)=r

 

Para toda expresión regular e es posible construir un autómata finito no determinista que acepte el lenguaje generado por dicha expresión regular. El algoritmo es recursivo y consta de los siguientes pasos:

  1. Si e = Φ, el autómata correspondiente es el que aparece en la figura 1.1 (a).

  2. Si e = λ, el autómata correspondiente es el que aparece en la figura 1.1  (b).

  3. Si e = a, a ∈Σ, el autómata correspondiente es el que aparece en la figura 1.1 (c).

Figura 1.1 Autómatas para expresiones regulares básicas

 

  4. Si e=r|sy tenemos los autómatas correspondientes a r y s, que representaremos como aparecen en la figura 1.2, el autómata correspondiente a la expresión r|s es el que aparece en la figura 1.3 (a).

Figura 1.2 Autómatas correspondientes a las expresiones r y s.

 

  5. Si e = rsy tenemos los autómatas correspondientes a r y s, que representaremos como aparecen en la figura 1.2, el autómata correspondiente a la expresión rs es el que aparece en la figura 1.3 (b).

Figura 1.3 Autómatas correspondientes a las expresiones r|s y rs.

 

 

  6. Si e = r*y tenemos el autómata correspondiente a r, que representaremos como aparece en la figura 1.4 (a), el autómata correspondiente a la expresión r* es el que aparece en la figura 1.4 (b).

Figura 1.4 Autómatas correspondientes a las expresiones r y r*.