Las aplicaciones de autómatas finitos deterministas

Las aplicaciones de autómatas finitos deterministas

Eric Gribkoff

ECS 120

UC Davis

Primavera 2013

1 determinista autómatas finitos

Determinista autómatas finitos, o DFA, tienen un fondo rico en términos de la teoría matemática subyacente a su desarrollo y uso. Esta base teórica es el énfasis principal de la cobertura de DFA de ECS 120. Sin embargo, este folleto se centrará en el examen de las aplicaciones del mundo real de DFA para obtener una apreciación de la utilidad de este concepto teórico. DFA utiliza incluir análisis de protocolos, texto el análisis, el comportamiento personaje de videojuego, análisis de seguridad, unidades de control de la CPU, natural procesamiento del lenguaje, y el reconocimiento de voz. Además, muchos simple (y no lo que los dispositivos mecánicos simples) se diseñan con frecuencia y implementado usando DFA, tales como ascensores, máquinas expendedoras, y los semáforos de tráfico y minúsculas.

Como muestran los ejemplos a continuación demostrarán, DFA, naturalmente se prestan a concisamente en representación de cualquier sistema que debe mantener una definición interna del Estado.

Nuestros ejemplos comienzan con máquinas expendedoras, que deben recordar cuánto dinero que el usuario tiene de entrada, y continuar con los ejemplos más complicados de videojuego agente de la IA y los protocolos de comunicación. Como nuestro último ejemplo, vamos a considerar la incorporación de máquinas de estados finitos en la búsqueda de código abierto Apache Lucene motor, donde se utilizan para implementar-autocompletado término de búsqueda.

Formalmente, un autómata finito determinista es un 5-tupla (Q, Σ, δ, q0, F) tal que:

1. Q es un conjunto finito llamado a los estados

2. Σ es un conjunto finito llamado el alfabeto

3. δ: Q × Σ → Q es la función de transición

4. q0 ∈ Q es el estado de inicio

5. F ⊆ Q es el conjunto de estados aceptar

También discutimos las máquinas de Mealy, que se suman a la expresividad de DFA por la producción de valores de salida en cada transición, donde la salida depende de la corriente Estado y de entrada. En lugar de aceptar o rechazar las cuerdas, máquinas de Mealy mapa una cadena de entrada a una cadena de salida. Pueden ser considerados como funciones que reciben una cuerdas y producir una cadena en respuesta. Formalmente, una máquina Mealey es un 6-tupla (Q, Σ, Γ, δ, ω, q0) tal que:

1. Q, Σ, δ, y q0 se definen como en un DFA.

2. Γ es un conjunto finito llamado el alfabeto de salida

3. ω: Q × Σ → Γ es la función de salida}

2 Una Lista no exhaustiva de las aplicaciones de DFA

• Máquinas expendedoras

• Semáforos

• Videojuegos

• análisis de texto

• Coincidencia de expresiones regulares

• Controladores CPU

• Análisis Protocolo

• Procesamiento del Lenguaje Natural

• Reconocimiento de voz

3 Máquinas expendedoras

La Figura 1 presenta un DFA que describe el comportamiento de una máquina expendedora que acepta dólares y cuartos, y cobra $ 1.25 por soda. Una vez que la máquina recibe un mínimo de $ 1,25, que corresponde a los estados de color azul en el diagrama, que permitirá al usuario seleccionar un refresco. Auto-bucles representan entrada ignorado: la máquina no dispensará un refresco hasta por lo menos 1,25 dólares ha sido depositado, y no va a aceptar más dinero una vez que ya ha recibido mayor o igual a $ 1,25.

Para expresar la DFA como 5-tupla, los componentes se definen como sigue:

1. Q = {$ 0.00, $ 0.25, $ 0.50, $ 0.75, $ 1.00, $ 1.25, $ 1.50, $ 1.75, $ 2.00} son los estados

2. Σ = {$ 0.25, $ 1.00, seleccione} es el alfabeto

3. δ, la función de transición, es descrita por el diagrama de estados.

4. q0 = $ 0,00 es el estado de inicio

5. F = ∅ es el conjunto de estados aceptar

4 AI en Video Juegos: Los fantasmas de Pac-Man

Máquinas de estados finitos se prestan a la que representa el comportamiento de los caracteres de control informático en los videojuegos. Los estados de la máquina corresponden a los comportamientos de los personajes, que cambian de acuerdo a diversos eventos. Estos cambios son modelados por transiciones en el diagrama de estado. Máquinas de estado ciertamente no son los medios más sofisticados

...