Máquina finita: teoría e implementación. Máquinas de estados finitos, como programar sin problemas Máquina de estados finitos con estados s a b

Máquina finita: teoría e implementación.

Una máquina de estados finitos es un modelo abstracto que contiene un número finito de estados de algo. Se utiliza para representar y controlar el flujo de ejecución de cualquier comando. La máquina de estados es ideal para implementar inteligencia artificial en juegos, produciendo una solución ordenada sin escribir código complejo y voluminoso. En este artículo veremos la teoría y también aprenderemos cómo usar una máquina de estados simple y basada en pilas.

Ya hemos publicado una serie de artículos sobre cómo escribir inteligencia artificial utilizando una máquina de estados finitos. Si aún no has leído esta serie, puedes hacerlo ahora:

¿Qué es una máquina de estados finitos?

Una máquina de estados finitos (o simplemente FSM - máquina de estados finitos) es un modelo informático basado en una máquina de estados hipotética. Sólo un estado puede estar activo a la vez. Por tanto, para poder realizar cualquier acción, la máquina debe cambiar de estado.

Las máquinas de estados se utilizan normalmente para organizar y representar el flujo de ejecución de algo. Esto es especialmente útil al implementar IA en juegos. Por ejemplo, para escribir el “cerebro” de un enemigo: cada estado representa algún tipo de acción (atacar, esquivar, etc.).

Una máquina de estados finitos se puede representar como un gráfico cuyos vértices son estados y las aristas son transiciones entre ellos. Cada borde tiene una etiqueta que indica cuándo debe ocurrir la transición. Por ejemplo, en la imagen de arriba puedes ver que la máquina cambiará el estado "deambular" al estado "atacar", siempre que el jugador esté cerca.

Estados de planificación y sus transiciones.

La implementación de una máquina de estados finitos comienza con la identificación de sus estados y las transiciones entre ellos. Imagine una máquina de estados que describe las acciones de una hormiga que lleva hojas a un hormiguero:

El punto de partida es el estado "buscar hoja", que permanece activo hasta que la hormiga encuentra la hoja. Cuando esto suceda, el estado cambiará a “ir a casa”. Este mismo estado permanecerá activo hasta que nuestra hormiga llegue al hormiguero. Después de esto, el estado cambia nuevamente a "buscar hoja".

Si el estado "buscar hoja" está activo, pero el cursor del mouse está cerca de la hormiga, entonces el estado cambia a "huir". Una vez que la hormiga esté a una distancia lo suficientemente segura del cursor del mouse, el estado volverá a cambiar a "buscar hoja".

Tenga en cuenta que cuando regrese a casa o fuera de casa, la hormiga no le temerá al cursor del mouse. ¿Por qué? Sino porque no existe una transición correspondiente.

Implementación de una máquina de estados finitos simple.

Se puede implementar una máquina de estados finitos utilizando una sola clase. Llamémoslo FSM. La idea es implementar cada estado como un método o función. También usaremos la propiedad activeState para determinar el estado activo.

Clase pública FSM ( var privada activeState:Función; // puntero al estado activo de la máquina función pública FSM() ( ) función pública setState(estado:Función) :void ( activeState = estado; ) función pública actualización() :void ( si ( estado activo ! = nulo ) ( estado activo(); ) ) )

Cada estado es una función. Además, se llamará cada vez que se actualice el marco del juego. Como ya se mencionó, activeState almacenará un puntero a la función de estado activo.

El método update() de la clase FSM debe llamarse en cada cuadro del juego. Y éste, a su vez, llamará a la función del estado que esté actualmente activo.

El método setState() establecerá el nuevo estado activo. Además, cada función que define algún estado del autómata no necesariamente pertenece a la clase FSM; esto hace que nuestra clase sea más universal.

Usando una máquina de estados

Implementemos una IA de hormiga. Arriba ya hemos mostrado un conjunto de sus estados y transiciones entre ellos. Ilustrémoslos nuevamente, pero esta vez nos centraremos en el código.

Nuestra hormiga está representada por la clase Ant, que tiene un campo cerebral. Esta es sólo una instancia de la clase FSM.

Clase pública Ant ( posición var pública:Vector3D; velocidad var pública:Vector3D; cerebro var pública:FSM; función pública Ant(posX:Número, posY:Número) ( posición = nuevo Vector3D(posX, posY); velocidad = nuevo Vector3D( -1, -1); Brain = new FSM(); // Comienza buscando la hoja. Brain.setState(findLeaf); * Hace que la hormiga busque hojas. * Hace que la hormiga vaya al hormiguero */ public function goHome() :void ( ) /** * Estado "runAway / public function runAway() :void ( ) public function update():void ( // Actualizar". la máquina de estado. Esta función llamará a la // función de estado activo: findLeaf(), goHome() o runAway() Brain.update( ); // Aplicando velocidad al movimiento de la hormiga.

La clase Ant también contiene propiedades de velocidad y posición. Estas variables se utilizarán para calcular el movimiento utilizando el método de Euler. La función update() se llama cada vez que se actualiza el marco del juego.

A continuación se muestra una implementación de cada método, comenzando con findLeaf(), el estado responsable de encontrar hojas.

Función pública findLeaf() :void ( // Mueve la hormiga a la hoja. velocidad = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distancia (Juego .instance.leaf, esto)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Estado goHome(): se utiliza para hacer que la hormiga se vaya a casa.

Función pública goHome() :void ( // Mueve la hormiga a la casa velocidad = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( Juego.instance.home, esto)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Y finalmente, el estado runAway() se usa al esquivar el cursor del mouse.

Función pública runAway() :void ( // Aleja la hormiga del cursor speed = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // ¿El cursor aún está cerca? ? if (distancia(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // No, ya está muy lejos. Es hora de volver a buscar la hoja. Brain.setState(findLeaf); ) )

Mejora de FSM: autómata basado en pila

Imaginemos que una hormiga de camino a casa también necesita huir del cursor del ratón. Así se verán los estados del FSM:

Parece un cambio trivial. No, este cambio nos crea un problema. Imagínese que el estado actual es "huir". Si el cursor del ratón se aleja de la hormiga, ¿qué debería hacer: ir a casa o buscar una hoja?

La solución a este problema es una máquina de estados basada en pilas. A diferencia del FSM simple que implementamos anteriormente, este tipo de FSM utiliza una pila para administrar estados. En la parte superior de la pila está el estado activo y las transiciones ocurren cuando se agregan o eliminan estados de la pila.

Y aquí hay una demostración visual del funcionamiento de una máquina de estados basada en pila:

Implementación de un FSM basado en pila

Una máquina de estados de este tipo se puede implementar de la misma manera que una simple. La diferencia será el uso de una serie de punteros a los estados requeridos. Ya no necesitamos la propiedad activeState, porque la parte superior de la pila ya apuntará al estado activo.

Clase pública StackFSM ( pila var privada:Array; función pública StackFSM() ( this.stack = new Array(); ) actualización de función pública() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction!= null) ( currentStateFunction(); ) ) función pública popState() :Función ( return stack.pop(); ) función pública pushState(estado:Función) :void ( if (getCurrentState() != estado) ( stack.push(estado) ; ) ) función pública getCurrentState(): Función (retorno pila.longitud> 0? pila: nulo;))

Tenga en cuenta que el método setState() ha sido reemplazado por pushState() (agregando un nuevo estado en la parte superior de la pila) y popState() (eliminando un estado en la parte superior de la pila).

Usando FSM basado en pila

Es importante tener en cuenta que cuando se utiliza una máquina de estados basada en pila, cada estado es responsable de ser eliminado de la pila cuando ya no es necesario. Por ejemplo, el estado attack() debería eliminarse de la pila si el enemigo ya ha sido destruido.

Public class Ant ( (...) public var Brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) Brain = new StackFSM(); // Comience buscando el cerebro hoja. pushState( findLeaf); (...) ) /** * Estado "findLeaf". * Obliga a la hormiga a buscar hojas */ public function findLeaf() :void ( // Mueve la hormiga a la hoja. velocidad = new Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y) if (distancia(Game.instance.leaf, this)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // No, ya está muy lejos. Es hora de volver a buscar hojas. Brain.popState(); ) ) (...) )

Conclusión

Las máquinas de estados son ciertamente útiles para implementar la lógica de la inteligencia artificial en los juegos. Se pueden representar fácilmente como un gráfico, lo que permite al desarrollador ver todas las opciones posibles.

Implementar una máquina de estados con funciones de estado es una técnica simple pero poderosa. Se pueden implementar tejidos de estados aún más complejos utilizando FSM.

Elementos de la teoría de los autómatas.

Plan:

1. El concepto de máquina, el principio de funcionamiento de la máquina.

2. Métodos para especificar máquinas de estados finitos.

3. Problemas generales de la teoría de los autómatas.

Información teórica

El hombre siempre se ha esforzado por facilitar su trabajo haciendo que algunos dispositivos mecánicos funcionen por sí mismo sin su propia intervención. Al principio eran cuentos de hadas, luego empezaron a convertirse en cosas cotidianas. Coches, televisores, lavadoras e industrias enteras funcionan sin intervención humana. Además, en la mayoría de los casos no se requiere intervención humana y, en algunos casos, dicha intervención puede provocar fenómenos negativos. El concepto de "ametralladora", como un dispositivo que realiza un determinado tipo de acción, ha sido interpretado durante mucho tiempo exactamente de esta manera.

El concepto de máquina, el principio de funcionamiento de la máquina.

Concepto máquina Se considera en dos aspectos:

1. Dispositivo automático, realizando algunas funciones sin participación humana directa. Una máquina automática es un dispositivo real, comprensible por qué y cómo funciona, al menos para aquellas personas que la diseñaron y fabricaron. Un automóvil, un tractor, un avión, un semáforo, un televisor, un teléfono: todos estos son máquinas automáticas. En este aspecto, una computadora debe entenderse como una máquina automática que funciona según un programa compilado por una persona.

2. Autómata – concepto matemático, que denota un modelo matemático de dispositivos técnicos reales. Una máquina automática es un dispositivo abstracto; no está claro por qué y cómo funciona y, en general, por qué puede funcionar. En este aspecto, la máquina es una “caja negra” que teóricamente es capaz de realizar determinadas acciones. Desde el punto de vista de las matemáticas, carece en absoluto de importancia qué, cómo y por qué produce determinadas acciones.

Cualquier autómata debe tener un determinado número de entradas, un determinado número de salidas y un determinado número de estados internos.

La teoría de los autómatas algebraicos es una rama de la cibernética teórica que estudia los autómatas discretos desde un punto de vista algebraico abstracto.

La teoría general de los autómatas contiene varias subsecciones. Dependiendo del tema de estudio, se divide en teoría abstracta de autómatas y teoría estructural de autómatas.

Teoría abstracta de los autómatas estudia las transiciones realizadas por un autómata influenciadas por señales de entrada, así como las señales de salida como resultado de estas transiciones.

Tema de estudio estructural La teoría de los autómatas es la estructura del autómata, así como la estructura de las señales de entrada y salida, por ejemplo, métodos de codificación de señales de entrada y salida, etc.

Definición de máquinas de estados finitos

Máquina- un modelo abstracto de un dispositivo que opera en tiempo discreto, que procesa una secuencia finita de señales de entrada y las convierte en una secuencia finita de señales de salida (reacciones).

Durante el funcionamiento de una máquina de estados finitos, un número finito de sus estados internos cambian sucesivamente, y el estado de la máquina en un determinado momento está determinado únicamente por las señales de entrada y salida. Estas máquinas representan la base de toda la tecnología informática moderna y de todo tipo de sistemas discretos de seguimiento y control automáticos.

El concepto de autómata es tan abstracto que es difícil decir cuándo una persona alguna vez se las arregló sin autómatas. Cualquier dispositivo se ajusta a la definición de rifle de asalto, incluidos aquellos que los pueblos primitivos usaban para cazar o arrojar piedras para proteger su hogar del enemigo.

Algoritmo– comprensible y Una instrucción formal exacta para el ejecutante, que define sin ambigüedades el contenido y la secuencia de operaciones que traducen un conjunto dado de datos de entrada en el resultado deseado.

Se cree que el primer dispositivo de software creado por el hombre fue un reloj. Los mecanismos de reloj, que utilizan un resorte que acciona engranajes y mecanismos de levas, engranajes y palancas, realizan una serie de acciones específicas. Un ejemplo de este tipo de mecanismo de reloj es el famoso reloj del Teatro Central de Marionetas de Moscú, donde impulsa a doce personajes de cuentos de hadas situados en la esfera.

Señalemos varios hechos históricos interesantes relacionados con los autómatas como dispositivos mecánicos.

1. El filósofo y alquimista alemán Alberto el Grande, de 1216 a 1246, creó un sirviente de "hierro", un autómata que desempeñaba las funciones de portero en la casa.

2. El astrónomo Johann Müller (Regiamontan) (1436-1476) creó un águila mecánica que, con la inclinación de la cabeza y el movimiento de las alas, saludó la entrada en Nuremberg del emperador del Sacro Imperio Romano Germánico Maximiliano II.

3. Mecánico Jacques de Vacanson (1709-1782): autor del primer telar automático del mundo. Creó la imagen de un pato mecánico, una copia exacta de su doble viviente: nadaba, se limpiaba las plumas y tragaba granos de la palma de su mano. Su flautista mecánico, que interpretó once piezas musicales, asombró a los que vivieron en aquellos años lejanos.

4. Inventor ruso del siglo XIX. A. M. Gamuletsky creó un gabinete mecánico completo, que contenía muchas máquinas que él mismo diseñó. También había una cabeza parlante de un hechicero y un Cupido tocando el arpa, que cautivó la imaginación de los contemporáneos.

5. La primera máquina sumadora primitiva fue diseñada en 1641 por Blaise Pascal. El impulso para el descubrimiento fue el tormento de su padre, el inspector de impuestos, inspector que trabajaba día y noche con grandes cálculos. Al inventar una máquina sumadora, el hijo de dieciocho años salvó a su padre de cálculos complejos y le dio al mundo la primera calculadora que sumaba y restaba números.

6. La primera máquina de ajedrez fue construida en 1890 por el ingeniero español Torres Quevedo. Una máquina así sólo podría jugarse en un final de torres (rey y torre contra el rey).

7. La primera computadora controlada automáticamente fue creada por Charles Bubbage en 1822. Él diseñó máquina calculadora, que tenía dispositivos de almacenamiento y aritmética. Estos dispositivos se convirtieron en prototipos de dispositivos similares para computadoras modernas.

Tipos de máquinas.

El autómata se puede interpretar como un dispositivo que realiza los procesos de recibir, convertir y transmitir energía, materiales o información de acuerdo con el programa incorporado en ellos, pero sin participación humana directa.

Cualquier máquina tiene la suya. conjuntos básicos, que incluyen: alfabeto de entrada, alfabeto de salida, conjunto de estados de la máquina.

Un rasgo característico de una máquina de estados finitos es la presencia memoria, que determina el estado de la máquina en función del tiempo. La manifestación externa de los distintos estados de la máquina es su reacción ante el mismo tipo de influencia (señales).

En el funcionamiento de máquinas de estados finitos, un concepto importante es tiempo.

Las máquinas se pueden clasificar según varios criterios.

1. Por tipo de actividad - Los autómatas se dividen en: información, control y computación.

Amáquinas de información incluyen una variedad de tablas de referencia, paneles informativos en estadios y dispositivos de alarma.

A maquinas de control Es habitual referirse a dispositivos para controlar un determinado proceso, entre los que se incluyen específicamente: un ascensor, un transportador, una máquina herramienta, una barrera.

A computadoras incluyen microcalculadoras, procesadores de computadora y otros dispositivos que realizan cálculos.

Sin embargo, estrictamente hablando, muchos autómatas son sistemas tan complejos que son simultáneamente autómatas computacionales, de control y de información.

2. Máquinas de estados finitos – Desde el punto de vista de la informática, se trata de autómatas que son convertidores de información discretos. Estos incluyen convertidores que contienen un conjunto finito de señales de entrada y salida finitas, así como un conjunto finito de estados internos.

3. Máquinas digitales- máquinas que convierten digital información. En un autómata de este tipo, las señales de entrada se dan en forma de un conjunto finito de símbolos instantáneos: su duración es tan corta que puede despreciarse. En un tiempo fijo, los símbolos de entrada se convierten y la salida sufre una transición abrupta de un estado a otro.

4. Autómatas abstractos - mostrando un conjunto de palabras del alfabeto de entrada incógnitaen conjunto de palabras del alfabeto de salida y.

Hay un autómata abstracto:

~ Matemático modelo,

~ Algoritmo acciones de alguna transformación de secuencias de código,

~ Ley transformando el alfabeto de entrada en el de salida.

5. Máquinas síncronas y asíncronas. Dependiendo de si la señal de entrada y la señal de cambio de estado se reciben simultánea o secuencialmente, las máquinas se dividen en máquinas síncronas y asíncronas.

En máquinas sincrónicas la duración de las señales de entrada y los tiempos de transición están coordinados entre sí. Se utilizan en sistemas informáticos, sistemas de control automatizados, etc.

En máquinas asíncronas La duración de las señales de entrada y el tiempo de las transiciones no son consistentes entre sí. Dependen de fuentes externas: varios eventos y intervalo de muestreo es variable (por ejemplo, en cerraduras de combinación). En las máquinas asíncronas, el siguiente cambio en los valores de las señales de entrada puede ocurrir solo si el proceso de transición causado por el cambio anterior en estas señales ha finalizado.

6. Los autómatas se dividen en autómatas finitos e infinitos. Si la clasificación se basa en capacidad de memoria, entonces la diferencia radica en si la máquina tiene final o infinito número de estados internos.

bajo el infinito Se suele entender por autómata una cierta idealización matemática de la idea de autómata, que tiene un número infinito de estados. La memoria de un autómata de este tipo puede aumentar potencialmente de forma indefinida. Por ejemplo, los famosos autómatas abstractos de Post y Turing son autómatas infinitos, pero la computadora misma o sus partes individuales son autómatas finitos.

7. Los autómatas se dividen en autómatas deterministas y probabilísticos.. Si la clasificación se basa en mecanismo de selección aleatoria, Luego se hace una distinción entre autómatas deterministas y probabilísticos (estocásticos).

En autómatas deterministas El comportamiento y la estructura en cada momento están determinados de forma única por la información de entrada actual y el estado de la propia máquina en el momento anterior.

En los autómatas probabilísticos, esta dependencia también está asociada con alguna elección aleatoria.

probabilístico Un autómata es un convertidor de información discreta, cuyo funcionamiento en cada momento depende únicamente de los estados de la memoria y se describe mediante leyes estadísticas.

8. Máquina automática universal. En la teoría de los autómatas se ha demostrado que para realizar diversas transformaciones de información basta con construir universal una máquina automática con la ayuda de un programa y codificación adecuada, capaz de solucionar cualquier problema.

El modelo matemático de un autómata digital con una entrada está especificado por cinco objetos:

INCÓGNITA- conjunto finito de símbolos de entrada, alfabeto de entrada:

X= (x 1 (t), x 2 (t), ..., x n (t));

Y- conjunto finito de símbolos de salida, alfabeto de salida:

Y=(y 1 (t), y 2 (t), ..., y n (t));

P~ conjunto finito de estados del autómata:

Q= (q 0 (t), q 1 (t), q 2 (t), ..., q n (t)), q 0- estado inicial;

δ(q, incógnita) - función de transición de la máquina de un estado a otro: ( q incógnita INCÓGNITA)®Q;

λ(q, incógnita) ~ función de salida de la máquina: ( q x X) ® y.

Así, la máquina de estados C= (X,Q, Y, δ, λ.) está determinada por relaciones de recurrencia

q(0) = q 0 , q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

t es un momento discretizado en el tiempo o es una imagen de una función monótona t:. t® N, y T- tiempo continuo ordinario, N es el conjunto de los números naturales.

Todas las horas de trabajo t se divide en un número finito de intervalos, en cuyo límite cambia el estado de la máquina. En este caso, t(Г 0): muestra el número de cambios que ocurrieron antes del momento Г 0.

Un ejemplo de muestreo es el cine ordinario: el tiempo se divide en intervalos de 1/24 de segundo. El ojo humano percibe la sucesión de cuadros discretos como un movimiento continuo.

9. Los autómatas síncronos se dividen en autómatas harinosos y autómatas de Moore.. Dependiendo de forma de organizar la función de salida Las máquinas síncronas se dividen en máquinas Mili. ( autómatas tipo I) y autómatas de Moore (autómatas tipo II).

En máquinas Mili- señal de salida y(t) incógnita(t) y condición q(t- 1) la máquina en el momento anterior (t- 1). El modelo matemático de tales autómatas es el sistema de ecuaciones:

q(t) = δ (q(t-1), x(t)) e y(t) = λ (q(t-1), x(t)),

En las máquinas de Moore señal de salida y(t) determinado únicamente por la señal de entrada incógnita(t) y condición q(t) en un momento dado t. El modelo matemático de tales máquinas es el sistema:

q(t) = δ (q(t-1), x(t)) e y(t) = λ (q(t)),

En tales máquinas, la función de salida depende únicamente del estado de la máquina en un momento dado y no depende de la señal de entrada. Por tanto, la cadena de entrada de dicho autómata se lee una vez de izquierda a derecha, escaneando los caracteres uno por uno. En un determinado momento, la máquina de estados finitos se encuentra en un determinado estado interno, que cambia después de leer el siguiente carácter. El nuevo estado se puede caracterizar por el símbolo de lectura y el estado actual.

10. Máquinas combinadas– hay autómatas en los que el símbolo de salida no depende de su estado y está determinado únicamente por los símbolos de entrada actuales, es decir en este autómata todos los estados son equivalentes. En un autómata de este tipo, la función de transición está degenerada; en principio no tiene importancia y permanece sin cambios durante el funcionamiento. Por tanto, un autómata combinacional mínimo tiene un solo estado.

11 lógico autómatas: hay autómatas cuyo alfabeto de entrada consta de 2 toneladas conjuntos de longitud binaria T, y la salida es de 2 n conjuntos binarios de longitud pag. Para combinacional lógico autómatas, la función de salida tiene la forma de un sistema norte funciones lógicas de t variables.

El resultado del funcionamiento de la máquina viene determinado por su estado final.

Hay varias opciones para especificar una máquina de estados finitos. Por ejemplo, una máquina de estados se puede especificar usando cinco parámetros: , donde:

La máquina comienza a trabajar en el estado q 0, leyendo un carácter a la vez de la cadena de entrada. El símbolo de lectura transfiere la máquina a un nuevo estado desde Q de acuerdo con la función de transición. Si, al finalizar la lectura de la palabra ingresada (cadena de símbolos), la máquina se encuentra en uno de los estados de aceptación, entonces la máquina “acepta” la palabra. En este caso, se dice que pertenece al lenguaje del autómata en cuestión. De lo contrario, la palabra se "rechaza".

Las máquinas de estados se utilizan ampliamente en la práctica, como en analizadores sintácticos, analizadores léxicos y pruebas de software basadas en modelos.

Otras formas de describir

1. Diagrama de estado ( o a veces gráfico de transición) - representación gráfica de un conjunto de estados y funciones de transición. Es un gráfico unidireccional cargado, cuyos vértices son los estados de la nave espacial, los bordes son transiciones de un estado a otro y los símbolos en los que ocurre esta transición. Si la transición del estado q1 al q2 se puede realizar ante la aparición de uno de varios símbolos, entonces todos ellos deben estar inscritos sobre el arco del diagrama (rama del gráfico).
2. tabla de transición- representación tabular de la función δ. Normalmente, en una tabla de este tipo, cada fila corresponde a un estado y cada columna corresponde a un carácter de entrada válido. En la celda en la intersección de la fila y la columna se escribe la acción que debe realizar la máquina si, en una situación en la que se encontraba en un estado determinado, recibió un símbolo determinado en la entrada.

Determinismo

Las máquinas finitas se dividen en deterministas y no deterministas.

Máquina determinista de estados finitos

• Un autómata finito determinista (DFA) es un autómata en el que para cada secuencia de símbolos de entrada solo hay un estado al que el autómata puede pasar desde el actual.
• Un autómata finito no determinista (NFA) es una generalización de uno determinista. El no determinismo de los autómatas se logra de dos maneras:

Si consideramos el caso en el que la máquina se especifica de la siguiente manera: , donde:

Luego aparece el tercer signo de no determinismo: la presencia de varios estados iniciales (de partida) del autómata.

Existe un teorema que establece que “Cualquier autómata finito no determinista se puede convertir en uno determinista de modo que sus lenguajes coincidan” (dichos autómatas se denominan equivalentes). Sin embargo, dado que el número de estados en un DFA equivalente en el peor de los casos crece exponencialmente con el número de estados del DFA original, en la práctica tal determinación no siempre es posible. Además, las máquinas de estados finitos con salidas generalmente no son determinables.

Debido a las dos últimas observaciones, a pesar de la mayor complejidad de los autómatas finitos no deterministas, los NFA se utilizan predominantemente para tareas relacionadas con el procesamiento de textos.

Autómatas y lenguajes regulares.

Para un autómata, se puede definir un lenguaje (un conjunto de palabras) en el alfabeto Σ que representa- estos son los nombres de las palabras, cuando se ingresan, la máquina pasa del estado inicial a uno de los estados del conjunto F.

Lenguajes de programación especializados

• El lenguaje Sequential Function Chart (SFC) es un lenguaje de programación gráfica ampliamente utilizado para programar controladores lógicos industriales (PLC).

En SFC, un programa se describe como una secuencia esquemática de pasos conectados por transiciones.

Desarrollo de modelos utilizando máquinas de estados finitos.

Las máquinas finitas permiten construir modelos de sistemas de procesamiento paralelo; sin embargo, para cambiar el número de procesos paralelos en dicho modelo, es necesario realizar cambios significativos en el modelo mismo. Además, un intento de desarrollar un modelo complejo en una máquina de estados finitos conducirá a un rápido aumento en el número de estados de la máquina, lo que en última instancia hará que el desarrollo de dicho modelo sea una tarea extremadamente tediosa. Como se señaló anteriormente, el último problema se puede resolver utilizando un autómata no determinista.

Notas

Ver también

• Lógica secuencial (lógica secuencial)

Campo de golf

• Teoría de los autómatas / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorenz, A. F. Petrenko, V. P. Chapenko // Teoría de la probabilidad. Estadística matemática. Cibernética teórica. - M.: VINITI, 1976. - T. 13. - P. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
• Aplicación de máquinas de estados finitos para resolver problemas de automatización.
• Un ejemplo de implementación de una máquina de estados finitos en Python para el marco Django

Fundación Wikimedia.

• 2010.
• Keynes, John Maynard

Diagrama de estado (teoría del autómata)

Vea qué es una “Máquina de Estados Finitos” en otros diccionarios: máquina de estados

- CA Modelo computacional que describe un autómata con un número finito de estados. Las CA se utilizan ampliamente en programación, por ejemplo, en analizadores léxicos de compiladores. Máquina de estados finitos Especificación de secuencia... ... máquina de estados

Vea qué es una “Máquina de Estados Finitos” en otros diccionarios:- modelo matemático de un dispositivo con memoria finita. Una máquina de estados procesa múltiples señales discretas de entrada en múltiples señales de salida. Existen máquinas de estados finitos síncronas y asíncronas. En inglés: Máquina de estados finitos Ver...

Diccionario financiero- baigtinis automatas statusas T sritis automatika atitikmenys: engl. autómata finito; máquina de estados finitos vok. endlicher Automat, m; Finalautomat, m rus. máquina de estados finitos, m pranc. final automático, m; automatizar fin, m; automatizar terminal, m;… … Automatikos terminų žodynas MÁQUINA DE ESTADOS FINITOS

- un autómata, que tiene muchos estados, así como muchas señales de entrada y salida, son finitos. K. a. Puede ser un modelo técnico. dispositivos (computadora, dispositivo de relé) o biol. sistemas (sistema nervioso animal idealizado). Importante... ...- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Diccionario inglés-ruso de ingeniería eléctrica e ingeniería energética, Moscú, 1999] Temas de ingeniería eléctrica, conceptos básicos EN autómata modular finito ... Guía del traductor técnico

máquina de estados de accesibilidad- (UIT T Y.1711). Guía del traductor técnico

Temas: telecomunicaciones, conceptos básicos EN máquina de estado de disponibilidadASM... Máquina de estados con memoria.

- Una máquina de estados finitos con memoria es un modelo matemático de un dispositivo cuyo comportamiento depende tanto de las condiciones de entrada como del estado anterior. Para describir un autómata finito con memoria se utilizan los lenguajes de esquemas de operador, regulares... ... Wikipedia se utiliza máquina determinista de estados finitos Guía del traductor técnico

- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Diccionario inglés-ruso de ingeniería eléctrica e ingeniería energética, Moscú, 1999] Temas de ingeniería eléctrica, conceptos básicos EN autómata determinista finito ... maquina moore

- (autómata del segundo tipo) en la teoría de los cálculos, un autómata finito, cuyo valor de salida de la señal depende únicamente del estado actual del autómata dado, y no depende directamente, a diferencia del autómata Mealy, del valores de entrada. El autómata de Moore se llama... Wikipedia

En este artículo, el término "máquina de estados finitos" se refiere a un algoritmo que puede estar en uno de un pequeño número de estados. "Estado" es una determinada condición que define una relación determinada entre las señales de entrada y salida, así como las señales de entrada y los estados posteriores. Un lector inteligente notará inmediatamente que las máquinas de estados finitos descritas en este artículo son máquinas de Mealy. Una máquina Mealy es una máquina de estados finitos donde las salidas son funciones del estado actual y la señal de entrada, a diferencia de una máquina de Moore donde las salidas son funciones del estado únicamente. En ambos casos, el estado posterior es función del estado actual y de la señal de entrada.

Veamos un ejemplo de una máquina de estados finitos simple. Imagine que necesita reconocer la secuencia de caracteres “//” en una cadena de texto. La Figura 1 muestra cómo se hace esto usando una máquina de estados. La primera aparición de una barra diagonal no produce una señal de salida, pero hace que la máquina pase al segundo estado. Si en el segundo estado la máquina no encuentra una barra, vuelve al primero, ya que requiere la presencia de 2 barras seguidas. Si se encuentra la segunda barra, la máquina emite una señal de "listo".

Descubra lo que necesita el cliente.

Crear un diagrama de transición de estado

Asegúrese de que las transiciones funcionen correctamente.

Sea específico sobre los detalles de la transición.

Haz la prueba.

Ejemplo de máquina de estados

Veamos un ejemplo más interesante de máquina de estados: un programa que controla la retracción y extensión del tren de aterrizaje de un avión. Aunque la mayoría de los aviones realizan este procedimiento mediante un mecanismo de control electrohidráulico (simplemente porque no hay una computadora a bordo), en algunos casos, como en los vehículos aéreos no tripulados, vale la pena utilizar el control por software.

Primero, veamos el equipo. El tren de aterrizaje de la aeronave consta del tren de morro, el tren de aterrizaje principal izquierdo y el tren de aterrizaje principal derecho. Son accionados por un mecanismo hidráulico. Una bomba hidráulica accionada eléctricamente suministra presión al actuador de potencia. Usando el software, la bomba se enciende o apaga. La computadora ajusta la posición de la válvula de dirección - "abajo" o "arriba" - para permitir que la presión suba o baje el tren de aterrizaje. Cada uno de los soportes del chasis tiene un interruptor de límite: uno de ellos se cierra si el chasis está elevado, el otro, si está bloqueado en la posición baja. Para determinar si el avión está en tierra, un interruptor de límite en el puntal del tren de morro se cierra si el peso del avión está sobre el tren de morro. Los controles del piloto constan de un brazo superior/inferior del tren de aterrizaje y tres luces (una para cada pierna) que se pueden apagar, verde (posición abajo) o roja (posición de marcha).

Pasemos ahora al desarrollo de una máquina de estados finitos. El primer paso y el más difícil es comprender las expectativas reales del cliente. Una de las ventajas de una máquina de estados finitos es que obliga al programador a pensar en todos los casos posibles y, como resultado, a recibir toda la información necesaria del cliente. ¿Por qué considero que esta es la etapa más difícil? ¿Y cuántas veces te han dado una descripción de tarea similar a esta: no retraer el tren de aterrizaje si el avión está en tierra?

Por supuesto, esto es importante, pero el cliente cree que aquí termina todo. ¿Qué pasa con el resto de los casos? ¿Es suficiente retraer el tren de aterrizaje en el momento en que el avión despega del suelo? ¿Qué pasa si el avión rebota en un bache de la pista? ¿Qué pasa si el piloto coloca la palanca de cambios en la posición "arriba" mientras estaciona y, como resultado, comienza a despegar? ¿Debería elevarse el tren de aterrizaje en este caso?

Una de las ventajas de pensar en términos de una máquina de estados es que se puede dibujar rápidamente un diagrama de transición de estados en un tablero de proyección, justo en frente del cliente, y recorrer todo el proceso con él. Se acepta la siguiente designación para la transición de estado: "el evento que causó la transición"/"la señal de salida como resultado de la transición". Si solo hubiéramos desarrollado lo que el cliente pidió inicialmente (“no retraer el tren de aterrizaje si el avión está en tierra”), entonces habríamos recibido la máquina que se muestra en la Figura 2.

Al crear un diagrama de transición de estado (o cualquier otro algoritmo), tenga en cuenta lo siguiente:

Las computadoras funcionan muy rápidamente en comparación con los equipos mecánicos.

Es posible que el ingeniero mecánico que explica lo que hay que hacer no sepa tanto sobre computadoras y algoritmos como usted. ¡Y esto también es algo positivo, de lo contrario no te necesitarían!

¿Cómo se comportará su programa si se rompe una pieza mecánica o eléctrica?

En la Figura 3 se muestra una máquina de estados basada en lo que el cliente realmente requiere. Aquí queremos evitar que el tren de aterrizaje del avión se retraiga hasta que esté definitivamente en el aire. Para ello, después de abrir el interruptor de aterrizaje, la máquina espera unos segundos. También queremos responder al borde ascendente de la palanca del piloto en lugar de al nivel, lo que evitará problemas si alguien mueve la palanca mientras el avión está estacionado. Replegar o extender el tren de aterrizaje tarda unos segundos, y debemos estar preparados para la situación de que el piloto cambie de opinión durante esta operación y mueva la palanca en la dirección opuesta. Tenga en cuenta también que si el avión vuelve a aterrizar mientras estamos en el estado "Esperando despegue", el cronómetro se reiniciará y el tren de aterrizaje solo se retraerá si el avión está en el aire durante 2 segundos.

Implementación de una máquina de estados finitos.

El Listado 1 es mi implementación de la máquina de estados que se muestra en la Figura 3. Analicemos algunos detalles del código.

/*listado 1*/

enumeración typedef(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Tipo_estado;

/*Esta matriz contiene punteros a funciones llamadas en ciertos estados*/

vacío(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

Estado_tipo estado_actual;

InicializarLdgGearSM();

/*El corazón de la máquina es este bucle sin fin. Función correspondiente

Estado actual, llamado una vez por iteración */

mientras (1) {

tabla_estado();

DecrementTimer();

vacío InicializarLdgGearSM( vacío )

estado_actual = GEAR_DOWN;

/*Detener equipos, apagar luces, etc.*/

vacío Marcha abajo( vacío )

/* Pasa al estado de espera si el avión

No estaba en tierra y recibió la orden de levantar el tren de aterrizaje*/

si((gear_lever == ARRIBA) && (prev_gear_lever == ABAJO) && (squat_switch == ARRIBA)) (

estado_actual = WTG_FOR_TKOFF;

prev_gear_lever = palanca_de cambios;

vacío Engranaje elevado( vacío )

si((nosegear_is_up == HECHO) && (leftgear_is_up == HECHO) && (rtgear_is_up == HECHO)) (

estado_actual = GEAR_UP;

/*Si el piloto cambió su decisión, pasa al estado “tren de aterrizaje bajado”*/

si(palanca_de_cambios == ABAJO) (

curr_state = BAJAR_GEAR;

vacío Engranaje arriba ( vacío )

/*si el piloto movió la palanca a la posición “abajo”,

Pasamos al estado “tren de aterrizaje bajado”*/

si(palanca_de_cambios == ABAJO) (

curr_state = BAJAR_GEAR;

vacío WtgParaDespegue( vacío )

/* Espere antes de levantar el tren de aterrizaje.*/

si(minutero<= 0.0) {

curr_state = LEVANTAR_ENGRANAJE;

/*Si volvemos a tocarnos o el piloto cambia de opinión, empezamos de nuevo*/

si((squat_switch == ABAJO) || (palanca de cambios == ABAJO)) (

estado_actual = GEAR_DOWN;

/* No quiero exigirle que mueva la palanca nuevamente

Esto fue sólo un rebote.*/

prev_gear_lever = ABAJO;

vacío Engranaje de descenso( vacío )

si(palanca_de_cambios == ARRIBA) (

curr_state = LEVANTAR_ENGRANAJE;

si((nosegear_is_down == HECHO) && (leftgear_is_down == HECHO) &&(rtgear_is_down == HECHO)) (

estado_actual = GEAR_DOWN;

En primer lugar, puede observar que la funcionalidad de cada estado se implementa mediante una función C independiente. Por supuesto, sería posible implementar un autómata usando una declaración de cambio con un caso separado para cada estado, pero esto puede llevar a una función muy larga (10-20 líneas de código por estado para cada uno de los 20-30 estados). . Esto también puede provocar errores si cambia el código en las etapas finales de la prueba. Puede que nunca hayas olvidado una declaración de descanso al final de un caso, pero a mí me han sucedido casos así. El código de un estado nunca terminará en el código de otro si tiene una función separada para cada estado.

Para evitar el uso de una declaración de cambio, utilizo una matriz de punteros para indicar funciones y declaro que la variable utilizada como índice de la matriz es de tipo enum.

Para simplificar, el hardware de E/S responsable de leer el estado de los interruptores, encender y apagar las bombas, etc. se representa como variables simples. Se supone que estas variables son "direcciones mágicas" asociadas con el hardware a través de medios invisibles.

La otra cosa obvia es que el código realmente no importa en este momento. Simplemente pasa de un estado a otro. Este es un paso intermedio importante y no debe ignorarse. Por cierto, sería bueno agregar declaraciones de impresión entre directivas de compilación condicional (#ifdef DEBUG .. #endif) que imprimirían el estado actual y los valores de las señales de entrada.

La clave del éxito radica en el código que provoca la transición de estado, es decir. determina que se ha producido la entrada de datos.

Si el código pasa por todos los estados correctamente, el siguiente paso es escribir el “relleno” del código, es decir, exactamente lo que produce la señal de salida. Recuerde que cada transición tiene una señal de entrada (el evento que la causó) y una señal de salida (el dispositivo de E/S de hardware, como en nuestro ejemplo). A menudo resulta útil capturar esto en forma de una tabla de transición de estados.

En la tabla de transición de estado, hay una fila por transición de estado.

Al codificar una máquina de estados, intente preservar su solidez: una correspondencia clara entre los requisitos del cliente y el código. Puede ser necesario ocultar detalles de hardware en otra capa funcional, por ejemplo, para que el código de máquina de estados se parezca lo más posible a una tabla de transición de estados y a un diagrama de transición de estados. Esta simetría ayuda a prevenir errores y explica por qué las máquinas de estados son una parte tan importante del arsenal de un programador de sistemas integrados. Por supuesto, podría lograr el mismo efecto con casillas de verificación y un número infinito de declaraciones if anidadas, pero esto haría muy difícil rastrear el código y compararlo con los deseos del cliente.

El fragmento de código del Listado 2 amplía la función RaisingGear(). Tenga en cuenta que el código de la función RaisingGear() tiene como objetivo reflejar las 2 filas de la tabla de transición para el estado Raising Gear.

vacío Engranaje elevado( vacío )

/*Después de que se levantan todos los interruptores, pasamos al estado “chasis levantado”*/

si((nosegear_is_up == HECHO) && (leftgear_is_up == HECHO) && (rtgear_is_up == HECHO)) (

motor_bomba = APAGADO;

gear_lights = EXTINGUIR;

estado_actual = GEAR_UP;

/*Si el piloto cambia de opinión, comienza a replegar el tren de aterrizaje*/

si(palanca_de_cambios == ABAJO) (

dirección_bomba = ABAJO;

curr_state = GEAR_LOWERING;

Recuerde evitar condiciones latentes. Un estado oculto ocurre cuando, por pereza, intentas agregar un subestado condicional en lugar de agregar un estado específico. Por ejemplo, si su código procesa la misma señal de entrada de diferentes maneras (es decir, activa diferentes transiciones de estado) según el modo, entonces es un estado oculto. En este caso, me preguntaría si este estado debería dividirse en dos. El uso de estados ocultos anula el beneficio de utilizar una máquina de estados.

Como práctica, puedes extender la máquina de estados que acabamos de ver agregando un tiempo de espera al ciclo de retracción o extensión del tren de aterrizaje, porque... El ingeniero mecánico no quiere que la bomba hidráulica funcione más de 60 segundos. Si el ciclo termina, el piloto debe ser alertado mediante una luz verde y roja que se alterna, y debe poder mover la palanca nuevamente para intentarlo nuevamente. También se le puede preguntar a un hipotético ingeniero mecánico cuál es el efecto que tiene sobre la bomba invertir el sentido de una bomba mientras está funcionando, porque ocurre en dos casos cuando el piloto cambia de opinión. Por supuesto, el mecánico dirá que es negativo. Entonces, ¿cómo modificarías la máquina de estados para detener rápidamente la bomba al cambiar de dirección?

Prueba de máquina de estados

La belleza de codificar algoritmos como máquinas de estados es que el plan de prueba se escribe casi automáticamente. Todo lo que tienes que hacer es pasar por cada transición de estado. Normalmente hago esto con un marcador en la mano, tachando las flechas en el diagrama de transición de estado a medida que pasan la prueba. Esta es una buena manera de evitar "estados ocultos": se pasan por alto con más frecuencia en las pruebas que estados específicos.

Esto requiere mucha paciencia y mucho café, ya que incluso una máquina de estados de tamaño mediano puede tener hasta 100 transiciones diferentes. Por cierto, el número de transiciones es una excelente manera de medir la complejidad de un sistema. Esto último está determinado por los requisitos del cliente y la máquina de estados hace que el alcance de las pruebas sea obvio. Con un enfoque menos organizado, la cantidad de pruebas necesarias puede ser igual de impresionante, pero usted simplemente no lo sabrá.

Es muy conveniente utilizar declaraciones impresas en su código que muestren el estado actual y los valores de las señales de entrada y salida. Esto permite observar fácilmente lo que expresa la “Regla de Oro de las Pruebas de Software”: comprobar que el programa hace lo que está destinado a hacer, y también que no hace nada innecesario. En otras palabras, ¿está obteniendo sólo los resultados que espera y qué más está sucediendo más allá de eso? ¿Existen transiciones de estado “difíciles”, es decir? ¿Estados que pasan aleatoriamente por solo una repetición del ciclo? ¿Las salidas cambian cuando no esperas que lo hagan? Idealmente, la salida de su printfs debería parecerse notablemente a una tabla de transición de estado.

Finalmente, y esto se aplica a cualquier software integrado, no sólo al software basado en máquinas de estado, tenga mucho cuidado la primera vez que ejecute el software en hardware real. Es muy fácil equivocarse en la polaridad de la señal: "Oh, pensé que '1' significaba tren de aterrizaje arriba y '0' significaba tren de aterrizaje abajo". En muchos casos, mi asistente de hardware usaba un "interruptor de gallina" temporal para proteger componentes valiosos hasta que estaba seguro de que mi software estaba moviendo las cosas en la dirección correcta.

Lanzamiento

Cuando se cumplen todos los requisitos del cliente, puedo lanzar una máquina de estados de complejidad similar en un par de días. Casi siempre las máquinas hacen lo que quiero. Lo más difícil es, por supuesto, entender exactamente lo que quiere el cliente y asegurarse de que el propio cliente sepa lo que quiere. ¡Esto último lleva mucho más tiempo!

Martín Gómez es programador del Laboratorio de Física Aplicada de la Universidad Johns Hopkins. Comprometido en el desarrollo de software para apoyar vuelos de naves espaciales de investigación. Trabajó en el campo del desarrollo de sistemas embebidos durante 17 años. Martin tiene una Licenciatura en Ingeniería Aeroespacial y una Maestría en Ciencias en Ingeniería Eléctrica de la Universidad de Cornell.

El artículo analiza máquinas de estados finitos simples y su implementación en C++ utilizando construcciones de conmutadores, tablas de tiempo de ejecución y la biblioteca Boost Statechart.

Introducción

En términos generales, una máquina de estados finitos, a través de los ojos del usuario, es una caja negra a la que se puede transferir algo y recibir algo desde allí. Esta es una abstracción muy conveniente que le permite ocultar un algoritmo complejo, y las máquinas de estados finitos también son muy eficientes.

Las máquinas de estados finitos se representan en forma de diagramas que constan de estados y transiciones. Déjame explicarte con un ejemplo sencillo:

Como probablemente habrás adivinado, este es un diagrama de estado de una bombilla. El estado inicial se indica con un círculo negro, las transiciones con flechas, algunas flechas están etiquetadas; estos son eventos después de los cuales la máquina pasa a otro estado. Entonces, inmediatamente desde el estado inicial, nos encontramos en el estado Luz apagada– la lámpara no se enciende. Si pulsa el botón, la máquina cambiará de estado y seguirá la flecha marcada Pulsador, en un estado Luz encendida- la lámpara está encendida. Puede pasar de este estado, siguiendo nuevamente la flecha, después de presionar el botón, al estado Luz apagada.

Las tablas de transición también se utilizan ampliamente:

Aplicación práctica de las máquinas automáticas.

Las máquinas de estados finitos se utilizan ampliamente en programación. Por ejemplo, es muy conveniente imaginar el funcionamiento de un dispositivo en forma de máquina automática. Esto hará que el código sea más simple y fácil de experimentar y mantener.

Además, las máquinas de estados finitos se utilizan para escribir todo tipo de analizadores y analizadores de texto; con su ayuda, se pueden buscar subcadenas de manera efectiva y también se traducen a la máquina de estados finitos.

Por ejemplo, implementaremos un autómata para contar números y palabras en texto. Para empezar, acordemos que un número se considerará una secuencia de números del 0 al 9 de longitud arbitraria, rodeados por espacios en blanco (espacio, tabulación, salto de línea). Una palabra se considerará una secuencia de longitud arbitraria que consta de letras y también está rodeada de espacios en blanco.

Veamos el diagrama:

Del estado inicial llegamos al estado Comenzar. Comprobamos el carácter actual, y si es una letra, vamos al estado Palabra a lo largo de la flecha marcada como Carta. Este estado supone que actualmente estamos considerando una palabra; el análisis de otros símbolos confirmará esta suposición o la refutará. Entonces, considere el siguiente carácter, si es una letra, entonces el estado no cambia (observe la flecha circular marcada como Carta). Si el carácter no es una letra, sino que corresponde a un espacio en blanco, entonces esto significa que la suposición fue correcta y encontramos la palabra (seguimos la flecha Espacio agitado Comenzar). Si el carácter no es ni una letra ni un espacio, entonces cometimos un error en la suposición y la secuencia que estamos considerando no es una palabra (sigue la flecha Desconocido agitado Saltar).

Capaz de Saltar Estamos allí hasta que se encuentra un carácter de espacio en blanco. Una vez detectado un hueco, seguimos la flecha. Espacio agitado Comenzar. Esto es necesario para omitir por completo una línea que no coincida con nuestro patrón de búsqueda.

Después de ingresar al estado Comenzar, el ciclo de búsqueda se repite desde el principio. La rama de reconocimiento de números es similar a la rama de reconocimiento de palabras.

Autómata usando instrucciones de interruptor

El primero son los estados posibles:

Después de lo cual iteramos sobre la línea, deslizando el símbolo actual en la máquina. El autómata en sí es una instrucción de cambio que primero realiza una transición a la sección del estado actual. Dentro de la sección hay una construcción if-else que, dependiendo del evento (un símbolo entrante), cambia el estado actual:

for (size_t i = 0 ; i ! = length; ++ i) ( const char current = text[ i] ; switch (estado) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (actual)) (estado = State_Word;) break case State_Number: if (std:: isspace (actual)) ( Aquí miramos el diagrama: el estado actual. Número Espacio, evento

NúmeroEncontrado();

estado = Estado_Inicio;

) else if (! std::isdigit(current) ) ( state = State_Skip; ) break ;

case State_Word: if (std:: isspace (actual) ) ( FoundWord() ; estado = State_Start; ) else if (! std:: isalpha (actual) ) ( state = State_Skip; ) break ;

caso State_Skip: if (std::isspace (actual)) (estado = State_Start;) break;

) )

Facilidad de implementación para algoritmos simples

AddTransition(Estado_Inicio, Evento_Letra, Estado_Palabra);

AddTransition(Número_Estado, Espacio_Evento, Inicio_Estado); AddTransition(Número_Estado, Letra_Evento, Omisión_Estado); AddTransition(Número_Estado, Evento_Desconocido, Omisión_Estado); AddTransition(State_Word, Event_Space, State_Start); AddTransition(State_Word, Event_Digit, State_Skip);

NúmeroEncontrado();

AddTransition(State_Skip, Event_Space, State_Start);

Resultó bastante claro. El precio de la claridad será un funcionamiento más lento de la máquina, lo que, sin embargo, a menudo no importa.

Para que la máquina, cuando ocurran ciertos eventos, pueda notificar algún código, puedes agregarlo a la estructura con información sobre la transición (

Transición

) puntero de función (

Acción

NúmeroEncontrado();

), que se llamará:

typedef void (DynamicMachine:: * Acción) () ;

struct Transition (Estados BaseState_; Eventos Event_; Estados TargetState_; Acción Acción_;);

... void AddTransition(Estados del Estado, Evento de Eventos, Estados al Estado, Acción de Acción);

...AddTransition(Número_Estado, Espacio_Evento, Inicio_Estado y Máquina Dinámica::NúmeroEncontrado);

Flexibilidad y visibilidad

El resultado se logra a expensas del consumo de memoria.

Y los propios estados. Dentro de los estados, es necesario determinar el tipo que describe las transiciones ( reacciones), y si hay varias transiciones, inclúyalas en la lista de tipos boost::mpl::list. Segundo parámetro de plantilla estado_simple– tipo que describe la máquina. Las transiciones se describen mediante los parámetros de la plantilla de transición, un par Evento - Próximo estado:

estructura Palabra: impulso::statechart::simple_state

NúmeroEncontrado();

) ;

Saltar estructura: impulso::statechart::simple_state

( impulso de typedef::statechart::transición

reacciones;

) ;

)

La máquina está construida, solo queda inicializarla y ya podrás usarla: