Condições para a universalidade da NFA

Considere um autômato finito não determinístico $A = (Q, \Sigma, \delta, q_0, F)$ e uma função $f(n)$ . Adicionalmente, definimos $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$ .

Agora vamos analisar a seguinte declaração:

Se $\Sigma^{\leq f(|Q|)} \subseteq L(A)$ , então $L(A) = \Sigma^*$ .

É fácil mostrar que, para $f(n) = 2^n+1$ , é verdade; portanto, se os autômatos produzem todas as palavras com comprimento até $2^{|Q|}+1$ , então produz $\Sigma^*$ .

Mas ainda é válido se $f$ é um polinômio?

$A$$p$$\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$

Para que a declaração seja válida, f deve crescer exponencialmente, mesmo com o alfabeto unário.

[Editar: a análise foi ligeiramente aprimorada na revisão 2.]

Aqui está um esboço de prova. Suponha que a declaração mantenha e permita que f seja uma função tal que todo NFA com no máximo n estados que aceite todas as strings com comprimento no máximo f ( n ) aceite todas as strings. Vamos provar que para cada C > 0 e n suficientemente grande , temos f ( n )> 2 ^{C ⋅√ n} .

O teorema do número primo implica que para cada c <lg e e para k suficientemente grande , há pelo menos c ⋅2 ^k / k primos no intervalo [2 ^k , 2 ^{k +1} ]. Tomamos c = 1. Para tal k , deixe N _k = ⌈2 ^k / k ⌉ e defina um NFA M _{k da} seguinte maneira. Seja p ₁ ,…, p _{N k} números primos distintos no intervalo [2 ^k , 2 ^{k +1}] O NFA M _k tem S _k = 1 + p ₁ +… + p _{N k} estados. Além do estado inicial, os estados são particionados em N _k ciclos, onde o i- ésimo ciclo possui comprimento p _i . Em cada ciclo, todos os estados, exceto um, são aceitos. O estado inicial possui N _k arestas de saída, cada uma das quais passa para o estado imediatamente após o estado rejeitado em cada ciclo. Finalmente, o estado inicial também é aceito.

Seja P _k o produto p ₁ … p _{N k} . É fácil ver que M _k aceita todas as cadeias de comprimento menores que P _k, mas rejeita a cadeia de comprimento P _k . Portanto, f ( S _k ) ≥ P _k .

Observe que S _k ≤ 1 + N _k ⋅2 ^{k +1} = o (2 ^{2 k} ) e que P _k ≥ (2 ^k ) ^{N _k} ≥ 2 ^{2 k} . O resto é padrão.

EDITAR EM 10/12/06:

ok, essa é praticamente a melhor construção que posso obter, veja se alguém tem ideias melhores.

Teorema. Para cada Existe um NFA sobre os alfabetos com modo que a cadeia mais curta que não esteja em tenha comprimento .$n$$(5n+12)$$M$$\Sigma$$|\Sigma|=5$$L(M)$$(2^n-1)(n+1)+1$

Isso nos dará .$f(n) = \Omega(2^{n/5})$

A construção é praticamente igual à de Shallit , exceto que construímos um NFA diretamente em vez de representar o idioma por uma expressão regular primeiro. Deixei

$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$ .

Para cada , vamos construir uma linguagem de reconhecimento de NFA , em que é a seguinte sequência (considere por exemplo):$n$$\Sigma^*-\{s_n\}$$s_n$$n=3$

$s_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$ .

A idéia é que podemos construir um NFA consiste em cinco partes;

• um iniciador , que garante que a string comece com ;$\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$
• um terminador , que garante que a string termine com ;$\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$
• um contador , que mantém o número de símbolos entre dois 's como ;$\sharp$$n$
• um add one-verificador , que garante que apenas os símbolos com a forma aparece; finalmente,$\sharp{x \atop x+1}\sharp$
• um verificador consistente , que garante que apenas símbolos com o formato possam aparecer simultaneamente.$\sharp{x \atop y}\sharp{y \atop z}\sharp$

Observe que queremos aceitar vez de ; assim, quando descobrirmos que a sequência de entrada está desobedecendo a um dos comportamentos acima, aceitamos a sequência imediatamente. Caso contrário, apósetapas, o NFA estará no único estado possível de rejeição. E se a sequência for maior que, a NFA também aceita. Portanto, qualquer NFA que atenda às cinco condições acima rejeitará apenas .$\Sigma^*-\{s_n\}$$\{s_n\}$$|s_n|$$|s_n|$$s_n$

Pode ser fácil verificar a figura a seguir diretamente, em vez de uma prova rigorosa:

Começamos no estado superior esquerdo. A primeira parte é o iniciador e o contador, depois o verificador consistente, o terminador e, finalmente, o verificador de adição um. Todo o arco sem nós de terminal aponta para o estado inferior direito, que é um aceitador de todos os tempos. Algumas das arestas não são rotuladas devido à falta de espaços, mas podem ser recuperadas facilmente. Uma linha tracejada representa uma sequência de estados com arestas.$n-1$$n-2$

Podemos (dolorosamente) verificar se o NFA rejeita apenas , pois segue todas as cinco regras acima. Portanto, um NFA do estado com foi construído, o que satisfaz o requisito do teorema.$s_n$$(5n+12)$$|\Sigma|=5$

Se houver qualquer dúvida / problema com a construção, deixe um comentário e tentarei explicar / corrigir.

Essa questão foi estudada por Jeffrey O. Shallit et al. E, de fato, o valor ótimo de ainda está aberto para . (Quanto à linguagem unária, veja os comentários na resposta de Tsuyoshi )$f(n)$$|\Sigma|>1$

Nas páginas 46-51 de sua palestra sobre universalidade , ele forneceu uma construção que:

Teorema. Para para alguns grandes o suficiente, existe um NFA sobre alfabetos binários, de modo que a menor seqüência que não esteja em tenha comprimento para .$n\geq N$$N$$n$$M$$L(M)$$\Omega(2^{cn})$$c=1/75$

Portanto, o valor ótimo para está entre e . Não tenho certeza se o resultado de Shallit foi aprimorado nos últimos anos.$f(n)$$2^{n/75}$$2^n$