A ambiguidade constante pode reduzir a complexidade do estado de idiomas regulares?

Dizemos que NFA é constantemente ambíguo se existir modo que qualquer palavra seja aceita por ou (exatamente) caminhos. $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Se o autômato é constantemente ambíguo para , então é chamado FA não ambígua (UFA). $M$ $k=1$ $M$

Seja uma linguagem regular. $L$

Pode algum autômato constantemente ambíguo para ser menor que o menor UFA que aceita ? Quão menor poderia ser? $M_c$ $L$ $L$

O autômato finitamente ambíguo pode ser exponencialmente menor que o menor CFA para o mesmo idioma?

Sabe-se que existem autômatos finitamente ambíguos (existe , de modo que todas as palavras são aceitas por até caminhos) que são exponencialmente menores que o menor UFA para o mesmo idioma, mas não vejo algo sobre ambiguidade constante. $k$ $k$

Além disso, aqui está uma pergunta relacionada que eu publiquei aqui há alguns meses atrás.

EDITAR:

A resposta de Domotorp mostra que é polinomialmente redutível a , mas não aborda a questão de saber se podemos obter essa redução de espaço polinomial por s. $CFA$ $UFA$ $CFA$

Assim, a nova pergunta se torna: quanto menor (linear / quadraticamente / etc.) Uma ser comparada à mínima ? para o mesmo idioma? $CFA$ $UFA$

são

-transitions permitido?

ϵ

$\epsilon$

Denis

Talvez isso possa ser útil: em Kupke, Ao separar a constante da ambiguidade polinomial dos autômatos finitos, é apresentada a seguinte hierarquia:

Não verifiquei odocumento relacionadoporque está atrás do paywall.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Obrigado @MarzioDeBiasi, mas infelizmente isso não ajuda (também fiquei esperançoso ao ver a apresentação). Eles usam notação diferente da que eu uso (e eu já vi em trabalhos diferentes). A "constante ambiguidade" deles é o que chamei de ambiguidade finita; portanto, a relação entre o Cafa e a UFA já era conhecida por mim. Como meu aplicativo está contando soluções para problemas de NPC, minha linguagem é sempre finita e, como tal, todas as palavras são aceitas pelos caminhos

, que eles chamavam de "constante".

O (1)

$O(1)$

Gostaria de saber se minha definição ajuda a reduzir a complexidade do estado, pois tenho CFA que é exponencialmente menor que o menor UFA que eu conheço construir, e fiquei imaginando se é possível que não exista um UFA pequeno para o idioma.

@ Denis, sim, mas isso ajudaria a reduzir a complexidade do estado? Eu diria que você só pode reduzir o número de arestas com esses movimentos.

Respostas:

Afirmo que, para alguma linguagem, existe um CFA com estados e ou $s$ $0$ $c$ aceitando caminhos para cada palavra, existe um UFA com estados. A idéia básica é que os estados do UFA são as tuplas c (ordenadas) dos estados do CFA e ele aceita se e somente se todos os estados c aceitarem. É claro que também precisamos garantir que esses cálculos sejam realmente diferentes e que não contemos todos os permutações, portanto, para estes precisamos algum extra bits de armazenamento. $C_ss^c$ $c!$ $C_s$

Uma descrição um pouco mais detalhada da idéia básica: Se é um estado da UFA, ele passa a fazer uma transição (lendo uma letra ) para o estado se e somente se o CFA tiver uma transição (leitura da letra ) de para para cada . Um estado $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ é aceitar se e somente se está a aceitar para cada . Obviamente, o estado inicial do UFA é onde é o estado inicial do CFA. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

O problema com o exposto acima é que as execuções simuladas do CFA podem ser as mesmas. Então, adicionamos algumas informações extras, codificadas, digamos, em um gráfico em $c$ $c$ vértices que tem uma aresta entre vértice e vértice se durante a corrida até agora pelo menos uma vez tivemos que . $i$ $j$ $c_i\ne c_j$

Agora ainda temos um problema, que contamos tudo vezes devido às possíveis permutações. Podemos remediar isso exigindo que, se os -ésimo e ésimo estado fossem os mesmos até agora e no próximo passo eles diferissem, na próxima etapa o -ésimo estado deverá ter um índice maior. $c!$ $i$ $j$ $i$

domotorp
fonte

Obrigado por responder @domotorp. Infelizmente, não posso dizer que entendi. Você pode fornecer mais detalhes (por exemplo, como a prova da primalidade seria codificada?). Obrigado !

De qualquer forma, percebi que também existe um UFA para esse idioma, então esqueça. E a parte restante da minha resposta?

Domotorp #

Não tenho certeza se sigo. Se

for CFA com

, isso não significa que só pode haver caminhos

para cada palavra

, apenas que apenas

deles terminará em um estado de aceitação. Quais seriam os estados da UFA? Você pode tentar formalizá-lo?

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Lá vai você, espero que agora esteja claro.

Domotorp 11/06