Máquina estatal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de agosto de 2022; las comprobaciones requieren 6 ediciones .

Un autómata finito (KA) en la teoría de los algoritmos es una abstracción matemática , un modelo de un dispositivo discreto que tiene una entrada, una salida y está en un estado entre muchos posibles en un momento dado. Es un caso especial de un autómata discreto abstracto , cuyo número de estados internos posibles es finito .

Durante el funcionamiento, las acciones de entrada se reciben secuencialmente en la entrada del SC y en la salida, el SC genera señales de salida. Por lo general, bajo las influencias de entrada, la entrada del autómata se acepta como la entrada de símbolos de un alfabeto , y la salida del KA en el proceso de operación da símbolos en el caso general de un diferente, tal vez incluso sin intersección con el entrada, alfabeto.

Además de los autómatas finitos, también hay infinitos autómatas discretos: autómatas con un número infinito de estados internos, por ejemplo, una máquina de Turing .

La transición de un estado interno de la nave espacial a otro puede ocurrir no solo por influencias externas, sino también espontáneamente.

Hay autómatas KA deterministas, en los que el siguiente estado está determinado únicamente por el estado actual y la salida depende solo del estado actual y la entrada actual, y KA no deterministas , cuyo siguiente estado es generalmente indeterminado y, en consecuencia , la señal de salida no está definida. Si la transición a estados subsiguientes ocurre con ciertas probabilidades, dicha CA se denomina CA probabilística .

Cualquier sistema digital, por ejemplo, computadoras o algunos nodos lógicos de computadoras con disparadores de memoria y otros dispositivos , pueden servir como ejemplos de la implementación física de KA . La lógica secuencial combinacional no puede ser una CA, ya que no tiene estados internos (no tiene memoria).

Desde un punto de vista abstracto, CA estudia una parte de las matemáticas discretas : la teoría de los autómatas finitos .

La teoría de los autómatas finitos se usa ampliamente en la práctica, por ejemplo, en analizadores y lexers , pruebas de software basadas en modelos .

Descripción formal de la máquina de estado

Descripción formal general

Formalmente, el CA se define como cinco elementos ordenados de algunos conjuntos:

{\ estilo de visualización A = (S, X, Y, \ delta, \ lambda),}

donde es un conjunto finito de estados de autómatas;

S

X,Y

son los alfabetos finales de entrada y salida, respectivamente, a partir de los cuales se forman cadenas que el autómata lee y emite;

\delta :S\times X\rightarrow S

- función de transición;

\lambda :S\times X\rightarrow Y

es la función de las salidas.

Un autómata abstracto con algún estado seleccionado (este estado se llama estado inicial ) se llama autómata inicial . Dado que cada KA tiene un número finito de estados, y cualquiera de sus estados se puede asignar como estado inicial, el mismo autómata corresponde a los autómatas iniciales, es decir, el número de estados internos del KA. Así, una CA abstracta define una familia de autómatas iniciales. Si no se especifica el estado inicial, entonces el comportamiento del autómata siempre es no determinista, la palabra de salida del autómata depende del estado inicial, por lo que la descripción determinista completa del autómata será [1] : ${\ estilo de visualización s_ {0}}$ $norte$ $norte$

A=(S,X,Y,\delta,\lambda,s_{0}).

Hay dos clases de KA: autómatas de Moore - KA, en los que la señal de salida depende solo del estado interno, según la figura, el autómata de Moore no tiene conexión desde la entrada a la función de salida , y los autómatas Mealy - la señal de salida depende tanto del estado interno como del estado de la entrada. $x(t)$ $\lambda$

Descripción general

Hay varias formas de especificar el algoritmo para el funcionamiento de un autómata finito. Por ejemplo, un autómata finito se puede definir como cinco elementos ordenados de algunos conjuntos :

M=(V,Q,q_{0},F,\delta ),

donde está el alfabeto de entrada (un conjunto finito de símbolos de entrada ), a partir del cual se forman las palabras de entrada , percibidas por el autómata finito;

V

q

es el conjunto de estados internos ;

q_{0}

— estado inicial ;

(q_{0}\en Q)

F

- un conjunto de estados finales o finales ;

(F\subconjunto Q)

\delta

es una función de transición definida como un mapeo tal que , es decir, el valor de la función de transición en un par ordenado (estado, símbolo de entrada o cadena vacía de símbolos) es el conjunto de todos los estados a los que es posible una transición desde un estado dado para un símbolo de entrada dado o una cadena vacía de símbolos, generalmente denotada por la letra

\delta \colon Q\times (V\cup \{\varepsilon \})\rightarrow Q

\delta (q,a)=\{r\dos puntos q\,\,{\underset {a}{\to }}\,\,r\}

\varepsilon.

Al analizar CA, se acostumbra suponer que el autómata finito comienza en algún estado inicial , recibe secuencialmente un carácter de la palabra de entrada (una cadena de caracteres de entrada). El carácter de lectura puede transferir el autómata a un nuevo estado o no transferir a un nuevo estado de acuerdo con la función de transición. $q_{0}$

Al recibir una cadena de entrada de caracteres y hacer transiciones de estado a estado, el autómata después de recibir el último carácter $X$ [ aclarar ] la palabra de entrada estará en algún estado . ${\ estilo de visualización q'}$

Si este estado es final, se dice que el autómata ha aceptado la palabra $X$ [ aclarar ]

Otras formas de configurar el funcionamiento de la nave espacial

Estado inicial	siguiente estado
Estado inicial	Introduzca el carácter a	Introduzca el carácter b	Cualquier otro personaje
p0	p1	p0	p0
p1	p1	p2	p1
p2	p3	p4	p2
p3	p3	p5	p3
p4	p4	p4	p4
p5	p3	p5	p5

Un diagrama de estado (o, a veces , un gráfico de transición ) es una representación gráfica de un conjunto de estados y una función de transición. Es un gráfico dirigido etiquetado , cuyos vértices son los estados del KA, los arcos son las transiciones de un estado a otro, y las etiquetas de los arcos son los símbolos mediante los cuales se realiza la transición de un estado a otro. . Si la transición del estado q 1 a q 2 puede llevarse a cabo mediante uno de varios símbolos, entonces todos ellos deben etiquetarse sobre el arco del diagrama.
La tabla de transición es una 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. La celda en la intersección de la fila y la columna contiene el estado al que debe ir el autómata si lee el símbolo de entrada dado en este estado. A la derecha se muestra un ejemplo de una tabla de saltos para un autómata dado como un gráfico en la Figura 1.

Determinación

Las máquinas de estado se dividen en deterministas y no deterministas .

Un autómata finito determinista (DFA) es un autómata en el que no hay arcos con la etiqueta ε (una oración que no contiene un solo símbolo), y desde cualquier estado para cualquier símbolo, una transición a no más de un estado es posible.
Un autómata finito no determinista (NFA) es una generalización de uno determinista. El no determinismo de los autómatas se puede lograr de dos formas: o puede haber transiciones de un estado a otro causadas por una cadena vacía de símbolos, es decir, transiciones espontáneas sin influencias externas, o un KA puede pasar de un estado a diferentes estados. bajo la influencia del mismo símbolo.

Si consideramos el caso en que el autómata se especifica formalmente de la siguiente manera: , donde es el conjunto de estados iniciales del autómata, tal que , entonces aparece el tercer signo de no determinismo: la presencia de varios estados iniciales (de partida) para el autómata . ${\ estilo de visualización M = (V, Q, S, F, \ delta)}$ $S$ $S\subseteq Q$ $METRO$

teorema de determinación afirma que para cualquier máquina de estados finitos se puede construir una máquina de estados finitos determinista equivalente (se dice que dos máquinas de estados finitos son equivalentes si sus lenguajes son los mismos[ claro ] ). Sin embargo, dado que el número de estados en el DFA equivalente crece exponencialmente en el peor de los casos con el crecimiento del número de estados del NFA original, en la práctica tal determinación no siempre es posible. Además, los autómatas finitos con salida son generalmente indeterministas.

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

Autómatas y lenguajes regulares

Para un autómata finito, es posible definir un lenguaje (un conjunto de palabras) en el alfabeto que permite , es decir, se llaman las palabras cuya lectura traslada al autómata del estado inicial a uno de los estados finales. $V$

El teorema de Kleene establece que un lenguaje es regular si y solo si lo permite alguna máquina de estado utilizada en ese lenguaje.

Minimización de autómatas

Para cualquier lenguaje regular, existe un autómata único, salvo isomorfismo , que acepta este lenguaje y tiene el menor número posible de estados. El autómata mínimo para un lenguaje dado por un autómata finito determinista se puede implementar en tiempo polinomial, lo que permite optimizar el consumo de memoria necesario para trabajar con el autómata, así como resolver problemas como comprobar la equivalencia de dos autómatas en tiempo polinomial .

Lenguajes de programación especializados

El diagrama de función secuencial ( SFC ) es un lenguaje de programación gráfico ampliamente utilizado para programar controladores lógicos industriales ( PLC ).

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

Desarrollo de modelos utilizando máquinas de estados finitos

Los autómatas finitos le permiten construir modelos de sistemas de procesamiento paralelo, sin embargo, para cambiar la cantidad de procesos paralelos en dicho modelo, debe realizar cambios significativos en el modelo mismo. Además, un intento de desarrollar un modelo complejo implementado por un autómata finito conduce a un rápido aumento en el número de estados del autómata, lo que eventualmente hará que el desarrollo de dicho modelo lleve mucho tiempo. Como se señaló anteriormente, el último problema se puede resolver utilizando un autómata no determinista.

¿Qué pueden "hacer" una máquina de estados finitos y una máquina secuencial?

La respuesta se da en diferentes términos dependiendo de si el autómata (respectivamente, la máquina P) es autónomo o no [2] . Un autómata finito autónomo, a partir de un cierto ciclo, solo puede generar una secuencia periódica de estados x (respectivamente, una máquina P es una secuencia de símbolos de salida y ). Si esta secuencia consta de un solo símbolo, significa que el autómata alcanza un estado de equilibrio en un número finito de ciclos. Si esta secuencia contiene varios símbolos, esto significa que el autómata pasa sucesivamente por los estados correspondientes a estos símbolos, y luego la operación del autómata se repite periódicamente indefinidamente. Además, cualquiera que sea la secuencia periódica de estados de longitud finita, siempre se puede construir un autómata finito autónomo que, a partir del segundo ciclo, genere esta secuencia. Nada más, excepto la repetición periódica del mismo estado o una secuencia finita de estados, el autómata autónomo puede "hacer". Sin embargo, debido al hecho de que la ejecución secuencial de un ciclo dado de operaciones es típica de muchas áreas de la tecnología moderna, los sistemas dinámicos que, en una idealización aceptable, pueden considerarse como un autómata autónomo, son ampliamente utilizados.

Un ejemplo clásico son los autómatas títeres que realizan secuencias complejas de acciones, por ejemplo: escribir un determinado texto en un papel, tocar obras preestablecidas en el piano, etc.

Un ejemplo moderno son muchas máquinas automáticas, líneas automáticas y sistemas de control automático para la producción cíclica. Si el autómata no es autónomo, es decir, el estado de la entrada cambia de un ciclo a otro, entonces la respuesta a la pregunta de qué puede “hacer” y qué no puede “hacer” un autómata finito se puede dar en diferentes términos. Por ejemplo, la respuesta se puede formular en un lenguaje de representación de eventos. De hecho, un autómata finito no autónomo o una máquina secuencial solo transforma secuencias de caracteres de entrada en secuencias de caracteres de estado o de salida, y decir lo que un autómata finito puede y no puede "hacer" es averiguar qué transformaciones de secuencia son posibles en un autómata finito y que son imposibles. Pero dado que el número de estados (respectivamente, símbolos de salida) es finito, esta pregunta es equivalente a la siguiente pregunta: ¿en qué secuencias de entrada ocurre cada uno de los estados posibles (o cada uno de los símbolos de salida)? Esta última pregunta, en términos aceptados en la teoría de los autómatas finitos, se formula de la siguiente manera: qué eventos pueden y qué no pueden ser representados en un autómata finito por cada uno de los estados posibles (o por cada uno de los símbolos de salida).

La respuesta la dan los teoremas de Kleene . Esta respuesta es correcta, ya que los teoremas de Kleene establecen condiciones necesarias y suficientes para la representabilidad de una secuencia de eventos en un autómata, a saber: se distinguen conjuntos especiales de secuencias de símbolos de entrada - conjuntos regulares . El hecho de que aparezca una secuencia de entrada de tal conjunto se denomina evento regular correspondiente. Los teoremas de Kleene establecen que en un autómata finito solo se pueden representar eventos regulares. Así, en el lenguaje de la representación de eventos, la respuesta a la pregunta de qué puede “hacer” un autómata finito se da de manera inequívoca: un autómata finito solo puede representar eventos regulares. Un número importante de conjuntos de secuencias de entrada, con los que uno tiene que lidiar a menudo en la práctica, son obviamente regulares. Entonces, por ejemplo, se sabe que un conjunto que consta de cualquier número finito de secuencias de entrada de longitud finita es regularmente regular; el conjunto de cualquier secuencia de entrada periódica; un conjunto de secuencias infinitas que contiene secuencias finitas dadas durante los últimos ciclos, etc.

En el caso general, si se da un conjunto infinito de secuencias de entrada de alguna manera arbitraria, entonces queda abierta la cuestión de si este conjunto es regular. El punto es que el concepto de conjunto regular se introduce inductivamente, es decir, se establece un algoritmo para construir cualquier conjunto regular. Sin embargo, no existe una forma suficientemente eficiente de resolver el problema inverso, es decir, de determinar si cada conjunto dado es regular.

Aunque los teoremas de Kleene responden a la pregunta de qué puede hacer una máquina de estado, responden a esta pregunta de manera ineficiente. Se han hecho los primeros intentos de construir otros lenguajes en los que se pueda dar la respuesta de manera efectiva. Este problema del lenguaje, que juega un papel cardinal para obtener una respuesta efectiva a la pregunta de qué puede y qué no puede "hacer" un autómata finito, es también crucial para las primeras etapas de la síntesis de autómatas, es decir, para responder a la segunda de las preguntas anteriores. Si ampliamos la clase de sistemas dinámicos, que hemos definido con los términos "autómata finito" y "máquina secuencial", incluyendo la memoria infinita (el modelo de memoria infinita puede ser, por ejemplo, una cinta infinita para almacenar símbolos o una número infinito de estados), entonces para los sistemas dinámicos de esta clase más amplia (los sistemas abstractos de esta clase se llaman máquinas de Turing ) la respuesta a la pregunta "¿qué pueden hacer?" mucho más simple: pueden implementar cualquier algoritmo predefinido . Al mismo tiempo, el concepto mismo de algoritmo se interpreta en las matemáticas modernas como una implementación del cálculo de los valores de cualquier función recursiva . Una respuesta tan inequívoca y clara a la pregunta "¿qué puede hacer una máquina de Turing?" permite poner el concepto de máquina de Turing como base para la definición del concepto de algoritmo: un algoritmo es cualquier proceso que puede llevarse a cabo en un autómata finito complementado con memoria infinita, es decir, máquinas algorítmicamente completas, en una máquina de Turing, en una máquina de Post , etc.

Véase también

maquina mili
Subfusil moore
JFLAP - programa simulador multiplataforma (autómatas, máquinas de Turing, gramáticas)
Programación automática
Gráfico de función secuencial
Compilador
Traductor
redes de petri
Lógica secuencial (Lógica secuencial)
Tabla de decisiones
sufijo autómata

Notas

↑ Kuznetsov O. P., Adelson-Velsky G. M. Automata // Matemáticas discretas para un ingeniero. - M. : Energía, 1980. - 344 p.
↑ Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Autómatas. Algoritmos. Estado. edición Phys.-Math. Literatura 1963, 556 páginas.

Literatura

Belousov A. I., Tkachev S. B. Matemáticas discretas. - M. : MGTU, 2006. - S. 460-587. — ISBN 5-7038-2886-4 .
John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Matemáticas discretas. - 2ª ed. - Williams, 2002. - 528 págs. - (Algoritmos y métodos. El arte de programar).
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoría e implementación de lenguajes de programación - M.: MZ-Press, 2006, 2ª ed. — ISBN 5-94073-094-9
Teoría de autómatas / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Teoría de la probabilidad. Estadísticas matemáticas. Cibernética teórica. - M.: VINITI, 1976. - T. 13. - S. 109-188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
El uso de autómatas finitos para resolver problemas de automatización.
Glushkov V. M. Síntesis de autómatas digitales. — M.: GIFML , 1962. — 476 p.

Enlaces

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami

En catálogos bibliográficos	NKC : ph210246