Forma mínima de autómata

Un autómata mínimo  es un autómata que tiene el menor número posible de estados e implementa una función de salida dada. La tarea de minimizar un autómata se reduce a encontrar su forma mínima. Para un autómata finito arbitrario, se puede construir un autómata finito equivalente con el menor número de estados [1] .

Principio de construcción

La forma mínima de un autómata S (denotado como Š ) en la teoría de autómatas es un autómata con ň estados que forman el conjunto {σ 1 ..σ ň } . El autómata mínimo de S se construye de la siguiente manera. Las funciones características de los autómatas S y Š se denotan por g s , g z y g' s , g' z respectivamente. Entonces si , entonces .

Así, al construir Š de acuerdo con esta condición, no surge incertidumbre.

El algoritmo para encontrar el autómata mínimo fue propuesto por Aufenkamp y Hohn. Demostraron que para encontrar el autómata mínimo, es necesario encontrar particiones sucesivas P i del autómata S en clases 1, 2, ..., k, (k + 1)  - estados equivalentes entre sí, hasta que en algún paso (k + 1) no resulta que P k = P k+1 . Así, la partición P k da todas las clases de equivalencia de estados del autómata S . A todos los estados S pertenecientes a la clase de equivalencia Σ l se les puede asignar una designación general, por ejemplo, σ l . Por lo tanto, el autómata Š se obtiene del autómata S al "combinar" estados etiquetados de manera idéntica en un solo estado. Las formas en que se realiza esta unión dependen esencialmente de si el autómata se define como una tabla, un gráfico o una matriz.

Métodos para obtener la forma mínima

Tabla de saltos

Si se dan una tabla de transición y una partición equivalente Σ 1 ..Σ ň del autómata S , entonces la tabla de transición Š se puede construir de la siguiente manera:

1. Reemplace la designación de cada estado en la tabla S con la designación de la clase a la que pertenece este estado.
2. De cada grupo de líneas con las mismas designaciones en las celdas de la columna principal, tache todas las líneas excepto una.

La tabla resultante es la tabla de transición Š .

Gráfico de transición

Dado un gráfico de transición ( diagrama de estado ) y una partición equivalente Σ 1 ..Σ ň del autómata S , entonces el gráfico de transición Š se puede construir de la siguiente manera:

1. Reemplace la designación de cada estado en el gráfico de transición S con la designación de la clase a la que pertenece este estado.
2. Combine todos los estados etiquetados de forma idéntica (tratando los arcos de gráficos como "enlaces flexibles") y represente los estados combinados como un solo estado con una etiqueta común.
3. De cada grupo de arcos que tienen un estado inicial y final común, elimine todos menos uno.

El gráfico resultante será el gráfico Š .

Matriz de transición

Dada una matriz de transición y una partición equivalente Σ 1 ..Σ ň del autómata S , entonces la matriz de transición Š se puede construir de la siguiente manera:

1. Realizar una permutación simétrica y una partición simétrica [S] de manera que las filas (y las columnas) se agrupen según las clases de equivalencia S (se puede obtener la misma matriz por el método de partición de matrices equivalentes).
2. Reemplace todas las designaciones de fila (y columna) de cada grupo que represente una clase de equivalencia con una sola designación de esa clase.
3. Reemplace cada submatriz en la matriz dividida con una sola celda que contenga todos los pares de entrada-salida que están en cualquier fila de esta submatriz (todas las filas en cualquier submatriz contienen el mismo conjunto de pares de entrada-salida).

La matriz resultante es la matriz de transición Š .

Propiedades mínimas de formulario

Si Š es la forma mínima del autómata S , entonces:

1. Š es la única forma mínima hasta la notación de los estados
2. Š=S
3. No hay dos estados Š equivalentes
4. No existe un autómata equivalente a S y más pequeño (con menos estados) que Š .

Notas

1. ↑ Matemáticas discretas, 2006 , p. 534.

Literatura

• Gill A. Introducción a la teoría de los autómatas finitos. M.: Nauka, 1966. - 272 p.
• Belousov A. I., Tkachev S. B. Matemáticas discretas. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .