¿Hay algún autómata no finito?

35

En la teoría de los autómatas, todos leemos autómatas como autómatas finitos, desde el principio. Lo que quiero saber es, ¿por qué los autómatas son finitos? Para ser claros, ¿qué hay en un autómata que es finito: el alfabeto, el idioma, las cadenas hechas con expresiones regulares o qué? ¿Y hay (en teoría) algún autómata no finito?

parvin
fuente
1
Ciertamente no el lenguaje o las "cadenas hechas con expresiones regulares"; muchas expresiones regulares simples coinciden con un número infinito de cadenas (pero pueden ser reconocidas por un autómata finito.)
alexis
Hice una pregunta teniendo en mente una infinita
Palabras como Jared

Respuestas:

34

Todos los modelos de autómatas que normalmente encontrarás están finamente representados; de lo contrario, habría innumerables, lo que significa que no son capturados por los modelos completos de Turing. O, en CS-think, serían inútiles¹.

Los "autómatas finitos" se denominan finitos porque solo tienen un conjunto finito de configuraciones (la cadena de entrada a un lado). Los autómatas pushdown, por ejemplo, tienen una pila que puede tener contenido arbitrario: hay infinitas configuraciones posibles.


Nota bene: ¡Las configuraciones de PDA todavía están finitamente representadas! De hecho, cualquier modelo computacional que se encuentre dentro de la computabilidad de Turing tiene que tener configuraciones finitamente representables, de lo contrario, los TM no podrían simularlos.


  1. Conscientemente ignoro la hipercomputación aquí para el propósito de esta pregunta.
Rafael
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Raphael
32

El nombre completo es " autómata de estado finito". La parte crucial es que el estado del autómata puede caracterizarse completamente por un elemento de algún conjunto finito de estados discretos. Esto significa que si el estado (relevante) del autómata involucra una variable de valor real, hay un número infinito de estados potenciales (dejando de lado la finitud de las representaciones de coma flotante), y el autómata no es finito.

Esto podría no suceder nunca en la informática teórica, pero no es demasiado exótico en el dominio del modelado de secuencias de números reales. Los modelos ocultos de Markov se pueden usar para modelar una secuencia numérica como la salida de un sistema probabilístico que consiste en un filtro de salida para cada estado de un modelo de Markov (discreto, finito) con estados no observables. Los filtros calculan la siguiente salida de valor real a partir de un vector de las salidas anteriores (modelo "autorregresivo"), pero el modelo subyacente de Markov es finito ya que sus probabilidades de transición solo dependen del estado actual de Markov.

Sin embargo, este artículo ( texto completo ) desarrolla una variación en la que las probabilidades de transición también dependen del vector de números reales de salidas anteriores. El estado de este sistema es la combinación de un estado discreto de Markov y una tupla de números reales ("modelo de Markov de estado mixto"), por lo tanto, puede estar en un número infinito de estados diferentes.

En resumen, los autómatas no finitos están teóricamente bien definidos y, en ocasiones, incluso se encuentran.

alexis
fuente
1
Divulgación completa: soy uno de los autores del artículo mencionado. No estoy seguro de si eso se considera una divulgación adecuada o una autopromoción irrelevante ...
alexis
66
Creo que está perfectamente bien hacer referencia al trabajo propio cuando sea apropiado; si eres uno de los principales expertos en un tema, ¡nos alegra tenerte! - y una simple revelación como la tuya es suficiente. ¡Gracias!
Raphael
Los autómatas de estado finito no incluyen autómatas pushdown, ¿verdad? ¿Hay alguna razón particular hasta los estados de números reales? No estoy seguro de si me falta algo aquí sobre por qué este ejemplo obvio no funcionaría o si simplemente elegiste un ejemplo inusual en su lugar.
Mehrdad
1
Creo que está tratando de preguntarte por qué no usaste un sistema no convencional FSA más convencional como un autómata pushdown en lugar de saltar a algo así como variables de estado con valores reales.
user2357112 es compatible con Monica
1
Bueno, principalmente porque ese es el ejemplo que pensé. Pero también el "estado" de un modelo de Markov de estado mixto consiste en un número fijo de parámetros, pero todavía hay un número infinito de estados (definidos como posición actual + probabilidades de transición) porque algunos de los parámetros son números reales (pero afectan las transiciones, no solo la salida). En el caso de PDA, la falta de finitud proviene del tamaño ilimitado de la pila; pero todavía hay solo un número finito de reglas, que son de longitud finita, por lo que en un solo paso solo hay un número finito de posibles comportamientos.
alexis
19

En un autómata finito, hay bastante finitud: el número de estados, el tamaño del alfabeto subyacente y las longitudes de las cadenas aceptadas por la máquina.

Ciertamente, puede relajar la condición de finitud en estos permitiendo, por ejemplo, que la máquina tenga infinitos estados, pero si lo hace, la máquina resultante deja de ser interesante, en el sentido de que tales máquinas pueden diseñarse para aceptar cualquier idioma.

Rick Decker
fuente
¿Y qué pasa si solo el alfabeto es infinito? ¿Qué pasa si estamos trabajando con una expresión regular en números naturales, por ejemplo? ¿es eso posible?
parvin
8
Si el autómata es finito pero el alfabeto es infinito, entonces el autómata tendrá un número finito de transiciones fuera de cada estado. Cualquier carácter no asociado con una de las transiciones no será reconocido por el autómata. Como resultado, podría reemplazar el alfabeto infinito con un alfabeto finito que contenga solo los caracteres que aparecen en las transiciones del autómata, y el autómata aún aceptaría exactamente el mismo idioma.
Kevin - Restablece a Mónica el
3
@parvin No realmente. Necesitaría tener un número infinito de transiciones entre sus (número finito de) estados, lo que aún no puede representar. Si va por predicados (como "todas las entradas pares van de A a B, todas las entradas impares van de A a C"), básicamente divide su alfabeto en un número finito de clases de equivalencia.
Bergi
@ Kevin, eso depende de cómo se defina "número finito de transiciones". Considere una FSA ordinaria (finita), con el siguiente estado elegido de acuerdo con cualquier partición finita de los números naturales: por ejemplo, por el resto de la división por 7. O considere una situación similar que involucra números reales. El diagrama de estado es completamente finito, pero está bien definido sobre un alfabeto infinito.
alexis
@Parvin, diría que la respuesta es "sí" (ver mi comentario anterior).
alexis
10

De hecho, en la teoría de los autómatas (que se aparta mucho de los orígenes de Kleene, Rabin y Scott), hay muchas formas de autómatas que no son finitas. Esto surge por varias razones.

Los autómatas pushdown , por ejemplo, son autómatas que tienen un conjunto infinito de configuraciones (estas tienen un número finito de estados, pero la realidad es que deben considerarse como 'autómatas infinitos').

En la misma línea, hay otros ejemplos de autómatas infinitos para los cuales el espacio de estado es infinito, pero con mucha estructura. Por ejemplo, uno considera la clase de autómatas que tienen como espacio de estado un espacio vectorial (dimensión finita), y como funciones de transición mapas lineales (más algunas cosas iniciales y finales). Estos se conocen como autómatas ponderados sobre un campo base (debido a Schützenberger en 61). Estos pueden ser minimizados y probados para la igualdad. Otros ejemplos incluyen autómatas de registro (estos autómatas tienen un conjunto finito de registros y funcionan sobre un alfabeto infinito: pueden comparar letras con registros y almacenar letras en registros), y la forma más moderna de autómatas nominales(que tienen la misma expresividad, pero tienen mejores fundamentos y propiedades). El vacío de tales autómatas es decidible.

UNAunatutuuna, y un estado acepta si pertenece a L). También hay un objeto final (que tiene como idiomas de estados). La existencia de estos dos objetos es una forma de explicar a alto nivel por qué los autómatas deterministas pueden minimizarse y están estrechamente vinculados a la congruencia de Myhill-Nerode.

Para concluir, hay autómatas infinitos, pero los modelos que se estudian por primera vez en una conferencia son siempre los de estado finito.

Thomas Colcombet
fuente
2

Creo que la pregunta es asumir la conclusión de que no hay autómatas de estado infinito cuando los hay, simplemente no vale la pena mencionarlos.

En Automata Theory, existe una jerarquía de poderes de diferentes modelos virtuales. El que aprendí tenía 4 (que recuerdo, ha pasado algún tiempo), el que encontré en Wikipedia tiene 5. El más débil en cualquier autómata de estado finito, y el más fuerte son las máquinas de Turing. Existe un concepto de un nivel más poderoso que las máquinas de Turing que se llama hipercomputación. Muchas descripciones diferentes de máquinas virtuales caen en uno de estos niveles. Las máquinas de Turing son especialmente conocidas por numerosos modelos que tienen el mismo nivel de potencia computacional.

Un autómata de estado infinito, al menos uno formalmente definido, caerá en uno de estos niveles. Puede haber algo un poco interesante en mostrar cómo una determinada definición rigurosa de un autómata de estado infinito se ajusta a uno de estos niveles, pero aparte de eso, no sería de mucha utilidad dado que hay máquinas virtuales mucho más estudiadas que representan cada nivel . Es similar a cómo no hay mucho interés en una máquina de Turing de mil millones de cintas, ya que no sería más potente que una sola máquina de Turing de cintas, sino más complicado de manejar.

Ahora, si encontraste un autómata de estado infinito que no era equivalente a un nivel existente de la jerarquía, eso podría ser interesante. Pero sin eso, los autómatas de estado infinito ya están capturados dentro de la jerarquía existente, y dadas las complicaciones adicionales de tratar con el infinito, simplemente los evitamos de la misma manera que evitamos cualquier modelo de máquina de Turing demasiado complicado.

Lawtonfogle
fuente
2

La versión infinita (ingenua) de la máquina determinista de estados finitos es demasiado poderosa . Tal cosa sería capaz de "memorizar" cualquier idioma, por lo que no hay mucho que aprender al considerarlos.

Por ejemplo, sobre un alfabeto binario, considere un autómata en forma de un árbol binario completo de altura infinita. Cada posible cadena que podría considerar como entrada corresponde únicamente a un nodo del árbol, por lo que puede construir un decisor para cualquier idioma simplemente haciendo que los nodos correspondientes acepten estados.


fuente