Minimizando os autômatos que aceitam palavras

Qual é a abordagem padrão para minimizar o Büchi-Automata (ou também o Müller-Automata)? Transferir a técnica usual de palavras finitas, ou seja, definir dois estados como iguais se as palavras "acabando" dos estados aceitos forem iguais, não funcionará. Por exemplo, considere o Büchi-Automoton aceitando todas as palavras com um número infinito de a consistindo em dois estados, um inicial e um final, e o estado final é inserido cada vez que um a é lido e o estado inicial é inserido cada vez que um símbolo diferente é lido. Ambos os estados são considerados iguais pela definição acima, mas colapsá-los produz um autômato que consiste em um único estado e, assim, aceita todas as palavras.

fl.formal-languages automata-theory StefanH
fonte

Respostas:

Em geral, $\omega$ línguas -Regular não pode ter um DBW mínima único. Por exemplo, a linguagem "infinitamente muitos um e infinitamente muitos b da" tem dois DBWS 3 de estado (na imagem substituir $\neg a$ por $b$ ): Dois DBWs mínimos para o mesmo idioma

Como você pode ver, eles não são topologicamente equivalentes.

Portanto, o problema de minimização é mais difícil do que o caso finito e, de fato, é NP-completo .

Shaull
fonte

Eu encontrei três Büchi-Automata determinísticos em três estados, dois são estruturalmente muito semelhantes (eles apenas diferem pelas etiquetas em suas transições), mas você gostaria de fornecer suas máquinas apenas para comparação :) Obrigado pelo artigo!

StefanH

@Stefan - adicionou o exemplo.

Shaull

Também tenho a esquerda, mas também tenho uma diferente, publiquei como uma edição na minha pergunta.

StefanH

O autômato você adicionou está incorreta - que não aceita a palavra

(b a b)^{ω} = b a b b a b b a b b a b . . .

$(bab)^\omega=babbabbabbab...$

Shaull

DBWS considerando, eu queria saber se o problema ainda é difícil se considerarmos a

alfabeto, vamos dizer binário. O que você acha? E em relação aos estados equivalentes, não podemos de alguma forma limitar o número de estados equivalentes de que precisamos ?! Por exemplo, acredito que se possa vincular o número de estados com apenas uma seta de saída (rotulada como "true").

c o n s t a n t

$constant$

Bader Abu Radi

Essa questão gerou muita literatura na década de 80, em parte devido a uma má abordagem do problema. Esta é uma história bastante longa que tentarei resumir nesta resposta.

1. O caso das palavras finitas

Pode-se encontrar duas definições de um DFA mínimo na literatura. O primeiro é definir o DFA mínimo de um idioma regular como o DFA completo com o número mínimo de estados que aceitam o idioma. O segundo é mais longo para definir, mas é matematicamente mais atraente que o primeiro e fornece propriedades mais fortes.

$(Q, A, \cdot, i, F)$ $q \in Q$ $u \in A^*$ $i \cdot u = q$ $q \cdot a$ $q \in Q$ $a \in A$

${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$ ${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$ $\mathcal{A}_1$ $\mathcal{A}_2$ $\varphi:Q_1 \to Q_2$

$\varphi(i_1) = i_2$
$\varphi^{-1}(F_2) = F_1$
$q \in Q_1$ $a \in A$ $\varphi(q)\cdot a=\varphi(q\cdot a)$

$\varphi$ $|Q_2| \leqslant |Q_1|$ ${\cal A}_1$ ${\cal A}_2$ ${\cal A}_1$ ${\cal A}_2$ $L$ ${\cal A}_L$ $L$ $\cal A$ $L$ $\cal A$ ${\cal A}_L$ . Este autômato é chamado o DFA mínima de . Observe novamente que, como o número de estados em é menor que o número de estados em , também é mínimo no primeiro sentido. $L$ ${\cal A}_L$ $\cal A$ ${\cal A}_L$

Vale ressaltar que também existe uma definição algébrica adequada para DFAs incompletos . Veja [Eilenberg, Automata, Languages and Machines , vol. A, Academic Press, 1974] para mais detalhes.

2. Voltar para palavras infinitas

Estender a primeira definição não funciona, como mostra Shaull em sua resposta. E, infelizmente, também se pode mostrar que a propriedade universal da segunda definição não se estende a infinitas palavras, exceto em alguns casos particulares.

É o fim da história? Espere um segundo, há outro objeto mínimo que aceita idiomas regulares ...

3. A abordagem sintática

Voltemos primeiro a palavras finitas. Recorde-se que uma língua de é reconhecido por um monóide , se houver um sobrejetivo monóide morfismo e um subconjunto de de tal modo que . Mais uma vez, existe uma monóide , o chamado monóide sintática de , que reconhece e é um quociente de todos os monoides reconhecendo . Este monóide sintático pode ser definido diretamente como o quociente de pela congruência sintática de $L$ $A^*$ $M$ $f:A^* \to M$ $P$ $M$ $f^{-1}(P) = L$ $M(L)$ $L$ $L$ $L$ $A^*$ $\sim_L$ $L$ , definido da seguinte forma: A boa notícia é que desta vez, essa abordagem foi estendida a infinitas palavras, mas levou muito tempo para descobrir as noções apropriadas. Primeiro, a noção adequada de congruência sintática foi encontrada por A. Arnold (Uma congruência sintática para idiomas racionais , Theoret. Comput. Sci. 39 , 2-3 (1985), 333-335). A extensão dos monoides sintáticos para a definição de palavras infinitas exigia um tipo mais sofisticado de álgebras, hoje chamado álgebra de Wilke em homenagem a T. Wilke, que foi o primeiro a defini-las (T. Wilke, uma teoria algébrica para linguagens regulares de finito e infinito palavras,

u \sim_{L} v if and only if, for all x, y \in A^{*}, x u y \in L ⟺ x v y \in L

$\text{$u \sim_L v$ if and only if, for all $x, y \in A^*$, $xuy \in L \iff xvy \in L$}$

ω

$\omega$ Int. J. Alg. Comput. 3 (1993), 447-489). Mais detalhes podem ser encontrados no meu livro Palavras infinitas, em coautoria com D. Perrin.

4. Conclusão

Portanto, existe uma noção matematicamente sólida de um objeto mínimo que aceita uma determinada linguagem regular , mas não depende de autômatos. Este é realmente um fato bastante genérico: os autômatos são uma ferramenta algorítmica muito poderosa, mas nem sempre são suficientes para tratar questões matemáticas nas linguagens. $\omega$

J.-E. PIN
fonte