Estoy leyendo " Concatenación de idiomas regulares y complejidad descriptiva " de Galina Jiraskova, 2009 sobre la complejidad del estado resultante de la concatenación de dos idiomas regulares (por Galina Jiraskova), pero no puedo entender cuáles serían las implicaciones prácticas de la complejidad del estado. . El primer pensamiento trivial que me llamó la atención fue que una mayor complejidad requeriría más tiempo y espacio por parte de la máquina. ¿Es esto correcto? ¿También hay otros lugares donde la complejidad del estado es relevante y significativa?
Editar: La complejidad del estado de un lenguaje regular es el menor número de estados en cualquier autómata finito determinista (dfa) que acepta el lenguaje. La complejidad de estado no determinista de un lenguaje regular se define como el menor número de estados en cualquier autómata finito no determinista (nfa) para el lenguaje.
fuente
Respuestas:
La complejidad del estado se trata realmente de una descripción concisa de un objeto (en este caso, un lenguaje normal), no de la complejidad computacional. El tema general se llama "complejidad descriptiva" en la literatura y se inspira, en parte, en el clásico artículo de 1971 de Meyer y Fischer titulado "Economía de la expresión por autómatas, gramáticas y sistemas formales" (ver http: // people .csail.mit.edu / meyer / economy-of-description.pdf ). Esta sigue siendo un área activa, con una conferencia anual (DCFS - Complejidad descriptiva de los sistemas formales).
En cuanto a las aplicaciones, en cualquier lugar donde su programa se base esencialmente en una máquina de estados finitos (por ejemplo, analizadores) será bueno tener esta máquina de estados finitos lo más pequeña posible.
fuente
Permítanme agregar un ejemplo concreto a la excelente respuesta de Jeffrey Shallit.
Suponga que desea crear un diccionario Scrabble (TM). Puede pensar en varias formas de representar su diccionario, como una lista de palabras, intentos (árboles de letras) o autómatas deterministas. Según [1], minimizar un trie a un dawg [= DFA] produce un ahorro sorprendente en el espacio; El número de nodos se reduce de 117.150 a 19.853. El léxico representado como una lista de palabras crudas toma alrededor de 780 Kbytes, mientras que nuestro dawg puede representarse en 175 Kbytes.
Como puede ver, la complejidad del estado realmente importa en este caso, especialmente si desea escribir un programa eficiente como lo hicieron los autores.
[1] Appel y Jacobson , el programa de Scrabble más rápido del mundo , Comunicaciones de la ACM 31 , 572-578 (1988).
fuente
La prueba de que es decidible si una gramática arbitraria determinista libre de contexto (o equivalentemente un autómata determinista pushdown) tiene un autómata de estado finito equivalente que describe el mismo idioma es esencialmente una prueba de la complejidad del estado de autómatas finitos que describen lenguajes deterministas libres de contexto: El límite en el tamaño de estos autómatas finitos en términos de autómatas deterministas da límites a la duración del procedimiento de decisión.
Para obtener más detalles, consulte " Regularidad y problemas relacionados con los autómatas de pushdown deterministas ", de Leslie G. Valiant.
fuente