O significado da complexidade do estado em autômatos e linguagens regulares?

14

Estou lendo " Concatenação de idiomas regulares e complexidade descritiva ", de Galina Jiraskova, 2009, sobre a complexidade do estado resultante da concatenação de dois idiomas regulares (de Galina Jiraskova), mas não consigo entender quais seriam as implicações práticas da complexidade do estado. . O primeiro pensamento trivial que me ocorreu foi que uma complexidade mais alta exigiria mais tempo e espaço da máquina. Isso está correto? Também existem outros lugares onde a complexidade do estado é relevante e significativa?

Edit: A complexidade do estado de uma linguagem regular é o menor número de estados em qualquer autômato finito determinístico (dfa) que aceita a linguagem. A complexidade do estado não determinístico de uma linguagem regular é definida como o menor número de estados em qualquer autômato finito não determinístico (nfa) para a linguagem.

Airmine
fonte
Coisa certa. Editou a pergunta!
Airmine
Parece possível que o artigo que você está lendo responde à pergunta até certo ponto ...? Você pode citá-lo com mais detalhes, por exemplo, o título e, de preferência, um link para o pdf, se disponível? FSM complexidade estado aparece em muitas aplicações e também tem implicações teóricas ...
vzn
Sim, eu olhei o jornal e as referências. Não foi possível encontrar muito relacionado aos aplicativos de complexidade do estado.
Airmine
3
praticamente todos os aplicativos FSM (que existem muitos) devem considerar a complexidade do estado para problemas "triviais" não triviais. exemplo. Os FSMs são usados ​​no reconhecimento de fala, onde os estados são fonemas e isso pode levar a FSMs grandes. Os FSMs também são usados ​​extensivamente em aplicações de EE, por exemplo, circuitos, etc. um FSM com alta complexidade é um circuito "grande". no entanto, o papel em questão está em busca principalmente na complexidade teórica do problema onde superior / limites inferiores em "explosão" ou "minimização eficiente" (compressão) são propriedades essenciais para estudo ....
vzn
Não exatamente "prático", mas a complexidade do estado desempenha um papel na inferência baseada em diversidade de autômatos finitos de Rivest e Schapire: [conferência ; diário ].
Neal Young

Respostas:

18

A complexidade do estado é realmente uma descrição concisa de um objeto (neste caso, uma linguagem comum), não uma complexidade computacional. O tópico geral é chamado de "complexidade descritiva" na literatura e se inspira, em parte, no artigo clássico de 1971 de Meyer e Fischer, intitulado "Economia de expressão por autômatos, gramáticas e sistemas formais" (veja http: // people .csail.mit.edu / meyer / economia-de-descrição.pdf ). Essa ainda é uma área ativa, com uma conferência anual (DCFS - Complexidade Descritiva dos Sistemas Formais).

Quanto às aplicações, em qualquer lugar em que seu programa dependa essencialmente de uma máquina de estado finito (por exemplo, analisadores), será bom ter essa máquina de estado finito o menor possível.

Jeffrey Shallit
fonte
2
Ah, tudo bem. Então, basicamente, reduzir a complexidade do estado ajuda a obter uma representação mínima de um determinado idioma, em vez de facilitar o processamento?
Airmine
Além disso, como a maioria dos algoritmos de autômatos depende diretamente da complexidade do estado, a minimização de estados é frequentemente feita com um motivo ulterior de minimizar a complexidade computacional.
Denis
9

Permitam-me adicionar um exemplo concreto à excelente resposta de Jeffrey Shallit.

Suponha que você queira criar um dicionário Scrabble (TM). Você pode pensar em várias maneiras de representar seu dicionário, como lista de palavras, tentativas (árvores de letras) ou autômatos determinísticos. De acordo com [1], minimizar um trie para um dawg [= DFA] produz uma incrível economia de espaço; o número de nós é reduzido de 117.150 para 19.853. O léxico representado como uma lista de palavras brutas leva cerca de 780 Kbytes, enquanto nosso dawg pode ser representado em 175 Kbytes.

Como você pode ver, a complexidade do estado realmente importa nesse caso, especialmente se você deseja escrever um programa eficiente como os autores.

[1] Appel e Jacobson, o Programa de Scrabble mais rápido do mundo , Communications of the ACM 31 , 572-578 (1988).

J.-E. PIN
fonte
4

A prova de que é decidível se uma gramática determinística livre de contexto arbitrária (ou equivalente a um autômato de empilhamento determinístico) possui um autômato de estado finito equivalente que descreve a mesma linguagem é essencialmente uma prova da complexidade do estado de autômatos finitos que descrevem linguagens deterministas sem contexto: o limite do tamanho desses autômatos finitos em termos dos autômatos determinísticos dá limites à duração do procedimento de decisão.

Para obter detalhes, consulte " Regularidade e problemas relacionados a autômatos de empuxo determinísticos ", por Leslie G. Valiant.

Alex ten Brink
fonte