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

16

Dizemos que NFA é constantemente ambíguo se existir k N, de modo que qualquer palavra w Σ seja aceita por 0 ou (exatamente) k caminhos.MkNwΣ0k

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

Seja uma linguagem regular.L

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

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é k 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 U F A , mas não aborda a questão de saber se podemos obter essa redução de espaço polinomial por C F A s.CFAUFACFA

Assim, a nova pergunta se torna: quanto menor (linear / quadraticamente / etc.) Uma ser comparada à mínima U F A ? para o mesmo idioma?CFUMAvocêFUMA

RB
fonte
são -transitions permitido? ϵ
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. dfa2nunfa2ncafa2n???2npafa2nnfuma
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)
RB
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.
RB
11
@ 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.
RB

Respostas:

4

Afirmo que, para alguma linguagem, existe um CFA com estados e 0 ou cs0c 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 c ! permutações, portanto, para estes precisamos algum extra C s bits de armazenamento.Csscc!Cs

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 a ) para o estado ( s 1 , , s c ) se e somente se o CFA tiver uma transição (leitura da letra a ) de s i para s i para cada i . Um estado ( s 1 , , s c )(s1,,sc)a(s1,,sc)asisii(s1,,sc)é aceitar se e somente se está a aceitar para cada i . Obviamente, o estado inicial do UFA é ( s 0 , , s 0 ) onde s 0 é o estado inicial do CFA.sii(s0,,s0)s0

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 ccc vértices que tem uma aresta entre vértice e vértice j se durante a corrida até agora pelo menos uma vez tivemos que c ic j .Eujcicj

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

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 !
RB
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 k = c , isso não significa que só pode haver caminhos c para cada palavra w , apenas que apenas c deles terminará em um estado de aceitação. Quais seriam os estados da UFA? Você pode tentar formalizá-lo?Mk=ccWc
RB
Lá vai você, espero que agora esteja claro.
Domotorp 11/06