Algoritmos para minimizar os autômatos de Moore

O algoritmo de Brzozowski pode ser estendido aos autômatos de Moore, mas sua complexidade de tempo é exponencial em geral. Existe algum outro algoritmo para minimizar os autômatos de Moore? Quais são os tempos de execução desses algoritmos, se houver?

O algoritmo original de minimização do DFA foi projetado para Moore Machines , guiado por seu comportamento aparentemente mais observável. Mas o algoritmo apresentado aqui é uma reconstrução da minimização do DFA, desde que descobri as evidências históricas após o fato.

Após a Wikipedia (com algumas alterações notacionais):

Uma máquina de Moore pode ser definida como uma tupla de 6 consiste no seguinte:$(Q, q_0, \Sigma, \Pi, \delta, \gamma)$

• um conjunto finito de estados $Q$
• um estado inicial (também chamado estado inicial) que é um elemento de $q_0$$Q$
• um conjunto finito chamado alfabeto de entrada $\Sigma$
• um conjunto finito chamado alfabeto de saída $\Lambda$
• uma função de transição mapeando um estado e o alfabeto de entrada para o próximo estado $\delta : Q \times \Sigma \rightarrow Q$
• uma função de saída mapeando cada estado para o alfabeto de saída $\gamma : Q \rightarrow \Pi$

A partir dessa definição, uma máquina de Moore é um transdutor determinístico de estado finito.

Não tenho referência para minimização de autômatos de Moore. No entanto, não parece muito difícil imaginar um algoritmo, derivado do algoritmo usado para autômatos de estados finitos determinísticos.

A idéia na minimização do DFA é baseada na caracterização Myhill-Nerode de idiomas regulares .

Dada uma linguagem e um par de cadeias x e y , defina uma extensão distinta como sendo uma cadeia z, de modo que exatamente uma das duas cadeias x z e y z pertença a $L$$x$$y$$z$$xz$$yz$$L$ . Definir uma relação em cordas pela regra de que x R L y sse não há extensão diferencial para x e y . É fácil mostrar que R L é uma relação de equivalência em cordas, e, portanto, divide o conjunto de todas as cadeias em classes de equivalência.$R_L$$x R_L y$$x$$y$$R_L$

O Myhill-Nerode teorema afirma que é regular se e somente se R L tem um número finito de classes de equivalência, e além disso, que o número de estados no menor autômato finito determinístico (DFA) reconhecendo L é igual ao número de classes de equivalência em R L .$L$$R_L$$L$$R_L$

Com efeito cada estado do menor DFA é tal que W q tal como definido acima, é uma das classes de equivalência para a relação R L .$q$$W_q$$R_L$

Para um DFA não mínimo para a linguagem regular , é fácil mostrar que cada conjunto W q contém cadeias que todos pertencem a uma mesma classe equivalente com respeito a R L .$L$$W_q$$R_L$

Portanto, a minimização do DFA realmente consiste na mesclagem de estados (considerados como conjuntos de cadeias equivalentes), sempre que é mostrado que dois estados distintos contêm cadeias equivalentes.

Existem dois algoritmos razoavelmente rápidos para esse fim: o algoritmo de Moore (1956), que está no tempo e o algoritmo de Hopcroft (1971), no tempo O ( n log n ) .$O(n^2)$$O(n\log n)$

A extensão para autômatos Moore é melhor compreendido na redefinição da relação de equivalência de para um transdutor T . A relação R L estava preocupado com o facto de entrada futuro conduziria equivalente a um estado de aceitação. O R T relação de equivalência de autômatos Moore está preocupado com o fato de entrada futuro irá produzir o mesmo resultado.$R_T$$T$$R_L$$R_T$

Portanto, dado um transdutor e duas cadeias x e y , definimos uma extensão distinta como uma cadeia z tal que T ( x z ) = T ( x ) u e T ( y z ) = T ( $T$$x$$y$$z$$T(xz)=T(x)u$ com u ≠ v , ou seja, de modo que o comportamento de saída do transdutor seja diferente para z, dependendo de se está seguindo x ou y .$T(yz)=T(y)v$$u\neq v$$z$$x$$y$

Novamente, é uma relação de equivalência, dividindo todas as cadeias em Σ * em classes de equivalência. No caso de uma máquina Moore, essas classes corresponderão novamente ao estado do transdutor mínimo.$R_T$$\Sigma^*$

O algoritmo a seguir imita o algoritmo de Moore para minimizar o DFA.

Definimos uma partição inicial de Q em classes de estados S e da seguinte maneira:$\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Em seguida, dividimos as classes em seguinte maneira:$\mathcal P$

repita sucessivamente para cada classe de estados , até que nenhuma mude$S$
$\ \ $ repita $\forall a\in\Sigma,\;$
$\ \ \ \ $ Se , em seguida,fazer nadamaisdividida S em subconjuntos S i tal quepara cada subconjunto S i , existe uma classe diferente$\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$ tal que ∀ q ∈ S i$S'\in \mathcal P$ (os subconjuntos S i substituem S em P )$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $$S_i$$S$$\mathcal P$

Quando não há mais classe que precise ser dividida, as demais classes de estados formarão os estados da máquina mínima de Moore.

Por construção, todos os estados de uma classe têm a mesma saída que é a saída da classe.

Da mesma forma, para qualquer entrada , todos os estados de uma classe vão para algum estado da mesma outra classe, que define a função de transição para a máquina mínima de Moore.$a\in\Sigma$

Análise de complexidade: Seja seja o número de estados es = | Σ | o tamanho do alfabeto de entrada. O loop principal é executado no máximo $n=|Q|$$s=|\Sigma|$
$n$ vezes, pois cada iteração deve dividir pelo menos uma classe de estados e cada classe contém pelo menos um estado. Cada iteração do loop examina cada estado um número finito de vezes e proporcional ao número de símbolos de entrada. Portanto, a complexidade do algoritmo é , a mesma que a do algoritmo de minimização do DFA, que serviu de orientação para este.$O(sn^2)$

Não tenho nenhuma referência para essa minimização de máquinas Moore. Possivelmente está incluído em seu artigo:

Moore, Edward F. (1956). "Experimentos de Gedanken em máquinas seqüenciais". Estudos de Autômatos , Anais de Estudos Matemáticos (Princeton, NJ: Princeton University Press) (34): 129-153.

Este artigo é a principal referência que apresenta as Máquinas Moore . É também a referência para o algoritmo de minimização de DFA de Moore . Portanto, deveria ser surpreendente se a adaptação do algoritmo à minimização de Moore Machines não fosse pelo menos sugerida nesse artigo. Eu verifiquei o artigo e a versão do algoritmo de minimização apresentada é realmente para máquinas Moore, não para DFA. O artigo está bem escrito, mas o estilo da época torna um pouco mais difícil de ler. É interessante ver que muitas das idéias da teoria de Myhill-Nerode das Máquinas de Estado Finito já estão esboçadas neste artigo.

O ( s n log n ) mais recente$O(sn\log n)$ algoritmo devido a John Hopcroft (1971) deve ser igualmente adaptável às máquinas de Moore. Não está claro que houvesse motivo para publicar essa adaptação em qualquer lugar, e o artigo de Hopcroft parece não ter referência às máquinas de Moore.

Uma versão do algoritmo de Brzozowski usando derivadas de expressões regulares é apresentada em [2], capítulo 12, seção 4, onde é creditada em [4]. Veja [1] e [3] para o caso mais geral de transdutores subsequentes (a terminologia está um pouco desatualizada e o termo transdutor seqüencial é provavelmente mais apropriado atualmente).

[1] C. Choffrut, minimizando transdutores subsequentes: uma pesquisa, Theoret. Comp. Sci. 292 (2003), 131-143.

[2] S. Eilenberg, Automata, Languages ​​and Machines, vol. A, Academic Press, 1974.

[3] J.-E. Pin, um tutorial sobre funções seqüenciais . (Slides)

[4] GN Raney, Funções seqüenciais, JACM 5 (1958), 177-180.

O algoritmo de Brzozowski é um ponto de partida ruim (se você estiver preocupado com o pior tempo de execução assintótico). Até a Wikipedia diz o seguinte:

Como Brzozowski (1963) observou, a reversão das bordas de um DFA produz um autômato finito não determinístico (NFA) para a reversão do idioma original e a conversão desse NFA em um DFA usando a construção padrão do conjunto de potências (construindo apenas os estados alcançáveis ​​de o DFA convertido) leva a um DFA mínimo para o mesmo idioma invertido. Repetir essa operação de reversão uma segunda vez produz um DFA mínimo para o idioma original. A complexidade do pior caso do algoritmo de Brzozowski é exponencial, pois existem linguagens regulares para as quais o DFA mínimo da reversão é exponencialmente maior que o DFA mínimo da linguagem [6], mas frequentemente apresenta um desempenho melhor do que o pior caso sugere.

O algoritmo possui tempo de execução exponencial de pior caso, mesmo no DFA, porque calcula um autômato para o inverso, que pode ter que ser exponencialmente grande. Portanto, seu problema não vem da extensão dos transdutores.

Tente adaptar outro algoritmo de minimização do DFA.