Conditions d'universalité NFA

Considérons un automate fini non déterministe et une fonction . De plus, nous définissons .$A = (Q, \Sigma, \delta, q_0, F)$$f(n)$$\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$

Analysons maintenant la déclaration suivante:

Si , alors .$\Sigma^{\leq f(|Q|)} \subseteq L(A)$$L(A) = \Sigma^*$

Il est facile de montrer que pour c'est vrai, donc si les automates produisent chaque mot avec une longueur jusqu'à , alors il produit .$f(n) = 2^n+1$$2^{|Q|}+1$$\Sigma^*$

Mais est-il toujours valable si est un polynôme?$f$

Sinon, à quoi pourrait ressembler une construction d'un NFA pour un polynôme , st ?$A$$p$$\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$

Pour que l'instruction tienne, f doit croître de façon exponentielle, même avec l'alphabet unaire.

[Edit: L'analyse est légèrement améliorée dans la révision 2.]

Voici un croquis de preuve. Supposons que l'instruction contienne et soit f une fonction telle que tout NFA avec au plus n états qui accepte toutes les chaînes de longueur au plus f ( n ) accepte toutes les chaînes que ce soit. Nous prouverons que pour tout C > 0 et n suffisamment grand , nous avons f ( n )> 2 ^{C ⋅√ n} .

Le théorème des nombres premiers implique que pour tout c <lg e et pour des k suffisamment grands , il y a au moins c ⋅2 ^k / k nombres premiers dans l'intervalle [2 ^k , 2 ^{k +1} ]. On prend c = 1. Pour un tel k , soit N _k = ⌈2 ^k / k ⌉ et définissons un NFA M _k comme suit. Soit p ₁ ,…, p _{N k} des nombres premiers distincts dans l'intervalle [2 ^k , 2 ^{k +1}]. Le NFA M _k a S _k = 1 + p ₁ +… + p _{N k} états. Hormis l'état initial, les états sont partitionnés en N _k cycles où le i ème cycle a une longueur p _i . Dans chaque cycle, tous les états sauf un sont des états acceptés. L'état initial a N _{k fronts} sortants, chacun passant à l'état immédiatement après l'état rejeté dans chaque cycle. Enfin, l'état initial est également accepté.

Soit P _k le produit p ₁ … p _{N k} . Il est facile de voir que M _k accepte toutes les chaînes de longueur inférieure à P _k mais rejette la chaîne de longueur P _k . Par conséquent, f ( S _k ) ≥ P _k .

Notez que S _k ≤ 1 + N _k ⋅2 ^{k +1} = o (2 ^{2 k} ) et que P _k ≥ (2 ^k ) ^{N _k} ≥ 2 ^{2 k} . Le reste est standard.

EDIT AU 10/12/06:

ok, c'est à peu près la meilleure construction que je puisse obtenir, voir si quelqu'un a de meilleures idées.

Théorème. Pour chaque Il existe un NFA sur les alphabets avec sorte que la chaîne la plus courte qui n'est pas dans soit de longueur .$n$$(5n+12)$$M$$\Sigma$$|\Sigma|=5$$L(M)$$(2^n-1)(n+1)+1$

Cela nous donnera .$f(n) = \Omega(2^{n/5})$

La construction est à peu près la même que celle de Shallit , sauf que nous construisons un NFA directement au lieu de représenter d'abord le langage par une expression régulière. Laisser

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

Pour chaque , nous allons construire un langage de reconnaissance NFA , où est la séquence suivante (prenez par exemple):$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$ .

L'idée est que nous pouvons construire un NFA se compose de cinq parties;

• un démarreur , qui garantit que la chaîne commence par ;$\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$
• un terminateur , qui garantit que la chaîne se termine par ;$\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$
• un compteur , qui maintient le nombre de symboles entre deux comme ;$\sharp$$n$
• un vérificateur d'add-one , qui garantit que seuls les symboles de la forme apparaissent; enfin,$\sharp{x \atop x+1}\sharp$
• un vérificateur cohérent , qui garantit que seuls les symboles de la forme peuvent apparaître simultanément.$\sharp{x \atop y}\sharp{y \atop z}\sharp$

Notez que nous voulons accepter au lieu de , donc une fois que nous découvrons que la séquence d'entrée désobéit à l'un des comportements ci-dessus, nous acceptons la séquence immédiatement. Sinon aprèsétapes, la NFA sera dans le seul état de rejet possible. Et si la séquence est plus longue que, la NFA accepte également. Ainsi, tout NFA remplit les cinq conditions ci-dessus ne rejettera que .$\Sigma^*-\{s_n\}$$\{s_n\}$$|s_n|$$|s_n|$$s_n$

Il peut être facile de vérifier directement la figure suivante au lieu d'une preuve rigoureuse:

Nous commençons à l'état supérieur gauche. La première partie est le démarreur et le compteur, puis le vérificateur cohérent, le terminateur, enfin le vérificateur add-one. Tout l'arc sans noeuds terminaux pointe vers l'état en bas à droite, qui est un accepteur de tous les temps. Certains bords ne sont pas étiquetés par manque d'espace, mais ils peuvent être récupérés facilement. Une ligne en pointillés représente une séquence de états avec arêtes.$n-1$$n-2$

Nous pouvons (douloureusement) vérifier que le NFA rejette uniquement, car il suit les cinq règles ci-dessus. Ainsi, un NFA -état avec a été construit, ce qui satisfait l'exigence du théorème.$s_n$$(5n+12)$$|\Sigma|=5$

S'il y a un manque de clarté / problème avec la construction, veuillez laisser un commentaire et je vais essayer de l'expliquer / le corriger.

Cette question a été étudiée par Jeffrey O. Shallit et al., Et en effet la valeur optimale de est toujours ouverte pour . (Quant à la langue unaire, voir les commentaires dans la réponse de Tsuyoshi )$f(n)$$|\Sigma|>1$

À la page 46-51 de son exposé sur l'universalité , il a fourni une construction telle que:

Théorème. Pour pour certains assez grands, il existe un NFA sur les alphabets binaires de telle sorte que la chaîne la plus courte qui n'est pas dans soit de longueur pour .$n\geq N$$N$$n$$M$$L(M)$$\Omega(2^{cn})$$c=1/75$

Ainsi, la valeur optimale pour se situe entre et . Je ne sais pas si le résultat de Shallit s'est amélioré ces dernières années.$f(n)$$2^{n/75}$$2^n$