AUTÓMATAS FINITOS

AUTÓMATAS FINITOS

Figura 2: Cinta de Entrada de AF

Definición: Un autómata finito es una estructura algebraica A = donde:

• Q : Conjunto finito de estados.

• : Alfabeto finito de entrada.

• : Función de transición : Qx P(Q)

• : Estado inicial, Q

• F : Conjunto de estados finales F Q

Definición de Configuración

Si A = es un AF, entonces (q,w) Q x es una configuración de A.

Configuración inicial: ( ,w)

Configuración final : (q, ),q F

Definición:

Si (q,a)=q' entonces (q,aw) (q',w) es un movimiento de A.

Un movimiento de A es representado por la relación binaria:

sobre configuraciones

+ movimiento transitivo de

hecho reflexivo transitivo de

Una cadena w es aceptada por un AFND, A si ( ,w) (q, ) para algún q F.

Un lenguaje aceptado por A es denotado por L(A) y es definido como:

L(A)={ w/w , ( ,w) (q, ), q F }

Ejemplos:

(1) Diseñe un AF para reconocer expresiones aritméticas de longitud arbitraria que comprenden enteros positivos separados por los signos de suma, resta, multiplicación o división.

Figura 3: AF de expresiones aritméticas

Q = {0,1}

={0,1,2,3,4,5,6,7,8,9,+,-,• ,:}

= {0}

F = {1}

(0,1+27:3-2) (1,+27:3-2) (0,27:3-2) (1,7:3-2) (1,:3-2) (0,3-2) (1,-2) (0,2) (1, ) Acepta porque está en configuración final.

(2) A =

Q = {0,1,2,3}

={a,b}

F = {3}

= 0

Figura 4: Autómata del ejemplo (2)

AUTÓMATAS FINITOS DETERMINÍSTICOS

Definición: A es determinístico si (q,a) no tiene más de un elemento q Q y a .

Si (q,a) tiene siempre exactamente un elemento A esta completamente especificado.

Teorema : Si L = L(A) para un AFND, A = entonces L = L(A') para un AFD, A'.

Se define un AFD A' = como sigue:

Q'=P(Q) ( )

= [ ]

F' = {B Q/ B F } (Todos los estados que contienen algún estado final)

'([ ,..., ],a) = [ ,..., ] ssi ({ ,..., },a) = { ,..., }

O sea ' aplicado a un elemento q' Q se calcula aplicando a cada estado de Q' representado por q' = [ ,..., ].

Al aplicar a cada ,..., y tomando la unión, se obtienen nuevos conjuntos de estados ,..., . Este nuevo conjunto tiene un representante [ ,..., ] Q' y ese elemento es el valor de '([ ,..., ],a).

Ejemplo: Tomando el AFND anterior

Q = {0,1,2,3} ={a,b} F =

...