Condições para a universalidade da NFA

28

Considere um autômato finito não determinístico A=(Q,Σ,δ,q0,F) e uma função f(n) . Adicionalmente, definimos Σk=ikΣi .

Agora vamos analisar a seguinte declaração:

Se Σf(|Q|)L(A) , então L(A)=Σ .

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

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

ApΣp(|Q|)L(A)Σ

Mike B.
fonte
Eu gostaria de dar uma recompensa a uma prova ou não prova de que para o caso . E se não houver, darei a melhor construção possível. f(n)=2no(n)|Σ|2
Hsien-Chih Chang,

Respostas:

22

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 1 ,…, p N k números primos distintos no intervalo [2 k , 2 k +1] O NFA M k tem S k = 1 + p 1 +… + 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 1p 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.

Tsuyoshi Ito
fonte
Qual é a sua conjectura sobre o melhor valor de ? Diga , ou algo entre e ? ff(n)=2n+12n2cn
Hsien-Chih Chang,
@ Hsien-Chih: Eu estava pensando a mesma coisa, e não tenho nenhuma conjectura razoável. Primeiro, é trivial ver f (n) ≤2 ^ n (não precisamos de +1) e, embora eu espere alguma melhoria linear sobre esse limite superior, não tenho idéia se é um fator constante. (mais)
Tsuyoshi Ito
(continua) Em segundo lugar, quanto ao limite inferior, se não me engano, um leve refinamento da análise acima fornece o seguinte limite inferior: para cada constante 0 <c < e n suficientemente grande, temos . Refinamentos adicionais provavelmente são possíveis, mas não podemos obter um limite inferior como 2 ^ {n ^ p} para p> 1/2 se usarmos a mesma construção do NTM. Penso que é uma questão interessante se o uso da distribuição de números primos (como o PNT) é essencial para a construção de maus exemplos. (mais)1/2f(n)>ecnlnn
Tsuyoshi Ito
(continua) No entanto, se você estiver interessado e quiser investigar mais, provavelmente é mais sábio procurar a literatura primeiro. Não ficarei surpreso se essa resposta ou algo melhor já tiver aparecido na literatura.
Tsuyoshi Ito
5
@ Tsuyoshi: É mostrado por Chrobak que um DFA de estado n para uma linguagem unária pode ser simulado por um NFA de estado para . Assim, sua construção é rígida se a linguagem for unária. Veja [Chr86]: cs.ust.hk/mjg_lib/Library/Chro86.pdfm=O(enlogn)
Hsien-Chih Chang,
19

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Σ|Σ|=5L(M)(2n1)(n+1)+1

Isso nos dará .f(n)=Ω(2n/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

Σ={[00],[01],[10],[11],} .

Para cada , vamos construir uma linguagem de reconhecimento de NFA , em que é a seguinte sequência (considere por exemplo):nΣ{sn}snn=3

s3=[00][00][01][00][01][10][11][11][01] .

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

  • um iniciador , que garante que a string comece com ;[00][00][01]
  • um terminador , que garante que a string termine com ;[11][11][01]
  • um contador , que mantém o número de símbolos entre dois 's como ;n
  • um add one-verificador , que garante que apenas os símbolos com a forma aparece; finalmente,xx+1
  • um verificador consistente , que garante que apenas símbolos com o formato possam aparecer simultaneamente.xyyz

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 .Σ{sn}{sn}|sn||sn|sn

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

NFA por rejeitar s_n

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.n1n2

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.sn(5n+12)|Σ|=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)|Σ|>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 .nNNnML(M)Ω(2cn)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)2n/752n

Hsien-Chih Chang 張顯 之
fonte
Estou brincando com o trabalho de Shallit, espero conseguir um melhor limite bem perto de . Sua construção parece interessante, especificando alguma sequência de comprimento que não pode ser representada por uma expressão regular "curta" de comprimento e cada expressão regular de comprimento pode ser descrito por um NFA do tamanho . Atualmente, sou capaz de deixar , mas é necessário chegar mais perto . 2nΩ^(2n)cn+o(n)f(n)f(n)+1c222n
Hsien-Chih Chang #
2
Não creio que ele dê mais informações para estudar esse problema, mas a referência acadêmica apropriada para a palestra de Shallit é: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Expressões regulares: novos resultados e problemas em aberto. Jornal de Automata, Idiomas e Combinatória 10 (4): 407-437 (2005)
Hermann Gruber
@Hermann: Obrigado pela referência, atualmente não consigo acessar o artigo, mas vou encontrar uma maneira de.
Hsien-Chih Chang
Acho que usando o contador , podemos substituir o motor de partida e o terminador por uma minúscula máquina de 2 estados. Portanto, isso reduz ainda mais o tamanho do NFA para . 3n+O(1)
Hsien-Chih Chang
1
A versão pré-impressa do autor do artigo JALC mencionado está aqui: cs.uwaterloo.ca/~shallit/Papers/re3.pdf O encadernado e a prova são os mesmos na versão impressa.
Hermann Gruber