Contando o número de palavras aceitas por uma NFA acíclica

Seja um NFA acíclico.$M$

Como é acíclico, é finito.$M$$L(M)$

Podemos calcularem tempo polinomial?$|L(M)|$

Se não, podemos aproximar?

Observe que o número de palavras não é igual ao número de caminhos aceitantes em , que é facilmente computável.$M$

Deixe-me mencionar uma abordagem óbvia que não funciona: converter o NFA em um DFA (que também será acíclico) e, em seguida, conte o número de caminhos de aceitação no DFA. Isso não resulta em um algoritmo de tempo polinomial, pois a conversão pode causar uma explosão exponencial no tamanho do DFA.

Aqui está uma abordagem que, espero, deve fornecer uma aproximação de fator multiplicativo, com tempo de execução polinomial.

Deixei $L$ ser um idioma comum que seja um subconjunto de $\{0,1\}^n$, por exemplo, $L=L(M) \cap \{0,1\}^n$. Vamos tentar calcular o tamanho aproximado de$L$.

Em um nível alto, nossa abordagem para aproximar $|L|$ será algo como isto:

1. Escolha uma fração $p$, Onde $0<p<1$.

2. Escolha um idioma regular $R$ de modo que, grosso modo, $R$ é um subconjunto aleatório de $\{0,1\}^n$ de tamanho aproximadamente $p2^n$ (ou seja, $|R|\approx p2^n$)

3. Verifique se $L \cap R$não está vazio. Observe que essa verificação pode ser feita em tempo polinomial.

Execute repetidamente as etapas 1 a 3 para vários valores de $p$. Isso fornece algumas informações que permitem aproximar$|L|$.

Em particular, se $|L|=m$, então esperamos

Portanto, se você escolher repetir as etapas 1 a 3 várias vezes, deve esperar ver um cruzamento vazio cerca de 37% das vezes. Se você vir uma interseção vazia significativamente mais frequentemente do que isso, aumente e tente novamente. Se você vir uma interseção vazia com menos frequência, poderá diminuir tentar novamente.$p=1/m$$p$$p$

Dessa forma, usando algo como pesquisa binária, você poderá aproximarpara dentro de um fator de aproximação multiplicativo.$|L|$

Você ainda precisará escolher uma maneira de escolher para que seja regular, mas também se comporte como um subconjunto aleatório. Existem muitas possibilidades, mas uma boa maneira seria escolher um hash 2-universal aleatório , escolha aleatoriamente e deixe . Escolher fornece um conjunto aleatório de aproximadamente o tamanho certo e, como é 2-universal, todas as matemáticas acima devem funcionar corretamente.$R$$h:\{0,1\}^m \to \{0,1,2,\dots,k-1\}$$y \in \{0,1,\dots,k-1\}$$R=\{x \in \{0,1\}^n : h(x)=y\}$$k=\lceil 1/p \rceil$$R$$h$

Isso deve resolver seu problema no caso em que todas as seqüências no NFA têm o mesmo comprimento, digamos . Se eles tiverem comprimentos variados, você poderá lidar com cada comprimento possível separadamente. Como é acíclico, o comprimento máximo de qualquer sequência em é no máximo o número de estados em , portanto, isso não aumenta muito o tempo de execução.$n$$M$$L(M)$$M$

(Essa construção pode lembrá-lo do teorema de Vazirani-Vazirani sobre SAT inequívoco.)

Suponha que você possa contar em tempo polinomial o número de palavras de um idioma fornecido por um NFA acíclico. Nesse caso, considerando dois NFAs acíclicos e , é possível calcular em tempo polinomial o cardinal (resp. ) do idioma de (resp. ). Por um produto direto (preservando a aciclicidade), você também pode calcular em tempo polinomial o cardeal da interseção dessas duas línguas. Os dois autômatos aceitam o mesmo idioma iff . Portanto, você pode testar a igualdade de duas linguagens finitas fornecidas pelos autômatos acíclicos no polinômio, que é conhecido por ser um problema completo do NP. Então, a menos que$A_1$$A_2$$n_1$$n_2$$A_1$$A_2$$n_3$$n_1=n_2=n_3$$P=NP$, você não pode resolver seu problema em tempo polinomial.