Autómata Finito Determinista

10/06/2011

Autómatas Finitos Deterministas
Lenguajes Formales y de Programación M.Sc. Luis Espino 2011

Basado en el capítulo 2 del libro: Introducción a la teoría de autómatas, lenguajes ycomputación. (J. Hopcroft, et al. 2002)

Autómatas Finitos
• Son modelos que describen lenguajes regulares, basado en las máquinas de estados. • Pueden dividirse en dos clases, basados en el control:▫ Deterministas: No puede estar en más de un estado simultáneamente. ▫ No deterministas: Puede estar en más de un estado simultáneamente.

Autómatas finitos deterministas
• Hace referencia alhecho de que, para cada entrada, existe un único estado al que el autómata puede llegar partiendo del estado actual. A= (Q, Σ, δ, q0, F)

Autómatas finitos deterministas
• Consta de:
▫ Un conjuntofinito de estados, Q. ▫ Un conjunto finito de símbolos de estrada, Σ. ▫ Una función de transición que recibe como argumentos un estado y una entrada, devuelve un estado. ▫ Un estado inicial, quepertenece a Q. ▫ Un conjunto de estados finales o de aceptación, subconjunto de Q.

Representaciones
• Especificación formal • Diagrama de transiciones • Tabla de transiciones

1

10/06/2011Especificación formal

Diagrama de transiciones
• Es un grafo definido de la siguiente forma:
▫ Hay un nodo por cada estado de Q. ▫ Para cada estado q de Q y cada símbolo de entrada del alfabeto hay unatransición de la forma: δ(q,a)=p ▫ Existe una flecha dirigida al estado inicial q0, con la etiqueta inicio. ▫ Los nodos de aceptación tiene doble círculo.

{w|w tiene la forma x01y, donde x e y soncadenas que solo constan de símbolos 0 y 1}

Ejemplo 1
• Dibujar un diagrama que muestre el autómata que genera todas las cadenas que contienen la sub cadena 01
▫ Ejemplos:  11101111  01  0010 0100  0111

2

10/06/2011

Tabla de transiciones
• Es una representación tabular convencional de una función delta que recibe argumentos y devuelve un valor. q0 q1 *q2 0 q1 q1 q2 1 q0...