Условия универсальности NFA

28

Рассмотрим недетерминированные конечные автоматы A=(Q,Σ,δ,q0,F) и функцию f(n) . Дополнительно определим Σk=ikΣi .

Теперь давайте проанализируем следующее утверждение:

Если Σf(|Q|)L(A) , то L(A)=Σ .

Нетрудно показать, что для f(n)=2n+1 это верно, следовательно, если автоматы генерируют каждое слово длиной до , то оно производит .2|Q|+1Σ

Но это все еще держится, если - многочлен?f

Если нет, то как может выглядеть конструкция NFA для данного полинома : st ?ApΣp(|Q|)L(A)Σ

Майк Б.
источник
Я хотел бы дать награду за доказательство или опровержение того, что для случая . А если его нет, я отдам его на лучшую конструкцию, какую только можно получить. | Σ | 2f(n)=2no(n)|Σ|2
Сянь-Чи Чан 張顯 之

Ответы:

22

Чтобы утверждение сохранялось, f должно расти экспоненциально, даже с унарным алфавитом.

[Редактировать: анализ немного улучшен в редакции 2.]

Вот примерный набросок. Предположим, что утверждение выполнено, и пусть f будет функцией, такой, что каждый NFA с не более чем n состояниями, который принимает все строки с длиной не более f ( n ), принимает все строки вообще. Докажем, что для любого C > 0 и достаточно большого n имеем f ( n )> 2 C ⋅√ n .

Из теоремы о простых числах следует, что для любого c <lg e и для достаточно больших k в интервале имеется не менее c ⋅ 2 k / k простых чисел [2 k , 2 k +1 ]. Мы берем с = 1. Для такого k пусть N k = k2 k / k ⌉ и определим NFA M k следующим образом. Пусть p 1 ,…, p N k - различные простые числа в диапазоне [2 k , 2 k +1]. NFA M k имеет S k = 1 + p 1 +… + p N k состояний. Помимо начального состояния, состояния делятся на N k циклов, где i- й цикл имеет длину p i . В каждом цикле все, кроме одного состояния, являются принятыми состояниями. Исходное состояние имеет N k исходящих ребер, каждый из которых переходит в состояние сразу после отклоненного состояния в каждом цикле. Наконец, начальное состояние также принимается.

Пусть P k - произведение p 1p N k . Легко видеть, что M k принимает все строки длиной меньше P k, но отклоняет строку длины P k . Следовательно, f ( S k ) ≥ P k .

Отметим, что S k ≤ 1 + N k ⋅2 k +1 = o (2 2 k ) и что P k ≥ (2 k ) N k ≥ 2 2 k . Остальное стандартно.

Цуёси Ито
источник
Каково ваше предположение о наилучшем значении ? Скажите f ( n ) = 2 n + 1 или где-то между 2 n и 2 c ff(n)=2n+12n ? 2cn
Сянь-Чи Чанг 之 之
@ Сянь-Чи: Мне было интересно то же самое, и у меня нет никаких разумных догадок. Во-первых, тривиально видеть, что f (n) ≤2 ^ n (нам не нужно +1), и, хотя я ожидаю некоторого линейного улучшения по сравнению с этой верхней границей, я не знаю, является ли она точной до постоянного множителя. (подробнее)
Цуёси Ито
(продолжение) Во-вторых, что касается нижней границы, если я не ошибаюсь, небольшое уточнение приведенного выше анализа дает следующую нижнюю оценку: для каждой константы 0 <c < и достаточно большое n, имеемf(n)>e c 1/2 . Дальнейшие уточнения, вероятно, возможны, но мы не можем получить нижнюю границу, такую ​​как 2 ^ {n ^ p} для p> 1/2, если мы используем ту же конструкцию NTM. Я думаю, что это интересный вопрос, является ли использование распределения простых чисел (таких как PNT) существенным для построения плохих примеров. (подробнее)f(n)>ecnlnn
Цуёси Ито
(продолжение) Однако, если вам интересно и вы хотите исследовать это дальше, возможно, разумнее сначала поискать литературу. Я не удивлюсь, если этот ответ или что-то лучшее уже появилось в литературе.
Цуёси Ито
5
@Tsuyoshi: Хробак показывает, что DFA с n-состоянием для унарного языка может быть смоделирован NFA с m-состоянием для . Таким образом, ваша конструкция жесткая, если язык унарный. См. [Chr86]:cs.ust.hk/mjg_lib/Library/Chro86.pdfm=O(enlogn)
Сянь-Чи Чанг 張顯 之
19

РЕДАКТИРОВАТЬ В 10/12/06:

хорошо, это в значительной степени лучшая конструкция, которую я могу получить, посмотрим, если кто-нибудь придумает лучшие идеи.

Теорема. Для каждого существует ( 5 n + 12 ) -состояния NFA M над алфавитами Σ с | Σ | = 5 так , что самая короткая строка, не входящая в L ( M ), имеет длину ( 2 n - 1 ) ( n + 1 ) + 1 .n(5n+12)MΣ|Σ|=5L(M)(2n1)(n+1)+1

Это даст нам .f(n)=Ω(2n/5)

Конструкция почти такая же, как у Шаллита , за исключением того, что мы создаем NFA напрямую, вместо того, чтобы сначала представлять язык регулярным выражением. Позволять

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

Для каждого мы собираемся построить язык распознавания NFA Σ - { s n } , где s n - следующая последовательность (например, n = 3 ):nΣ{sn}snn=3

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

Идея в том, что мы можем построить NFA состоит из пяти частей;

  • стартер , который обеспечивает строка начинается с ;[00][00][01]
  • терминатор , который обеспечивает струнные концы с ;[11][11][01]
  • счетчик , который хранит число символов между двумя «S , как п ;n
  • средство проверки add-one , которое гарантирует, что только символы с формой появляется x + 1 ;; Ну наконец то,xx+1
  • последовательная проверка , которая гарантирует , что только символы с формой могут появляться одновременно.xyyz

Обратите внимание, что мы хотим принять вместо { s n } , поэтому, как только мы узнаем, что входная последовательность не подчиняется одному из описанных выше способов поведения, мы немедленно принимаем последовательность. В противном случае после | с н | шаги, NFA будет в единственно возможном состоянии отказа. И если последовательность длиннее, чем | с н | НФА также принимает. Таким образом, любой NFA, удовлетворяющий вышеуказанным пяти условиям, будет отклонять только s n .Σ{sn}{sn}|sn||sn|sn

Может быть легко проверить следующую фигуру непосредственно вместо строгого доказательства:

NFA for rejecting s_n

Мы начинаем с верхнего левого состояния. Первая часть - это стартер, а затем счетчик, затем согласованный контролер, терминатор, и, наконец, проверка на добавление. Вся дуга без конечных узлов указывает на нижнее правое состояние, которое является постоянным акцептором. Некоторые края не помечены из-за отсутствия пробелов, но их можно легко восстановить. Штриховая линия представляет последовательность из состояний с n - 2 ребрами.n1n2

Мы можем (мучительно) проверить, что NFA отклоняет только , поскольку оно следует всем пяти вышеприведенным правилам. Итак ( 5 n + 12 ) -состояния NFA с | Σ | = 5 , что удовлетворяет требованию теоремы.sn(5n+12)|Σ|=5

Если есть какие-то неясности / проблемы со строительством, пожалуйста, оставьте комментарий, и я постараюсь объяснить / исправить это.


f(n)|Σ|>1

На странице 46-51 своего выступления об универсальности он представил такую ​​конструкцию, которая:

Theorem. For nN for some N large enough, there is an n-state NFA M over binary alphabets such that the shortest string not in L(M) is of length Ω(2cn) for c=1/75.

Thus the optimal value for f(n) is somewhere between 2n/75 and 2n. I'm not sure if the result by Shallit has been improved in recent years.

Hsien-Chih Chang 張顯之
источник
I'm playing with Shallit's work, hope to get a better bound much near 2n. Their construction seems interesting, by specify some sequence of length Ω^(2n) which can not be represent by a "short" regular expression of length cn+o(n), and each regular expression of length f(n) can be described by an NFA of size f(n)+1. Currently I'm able to let c22, but a smarter idea is need to come close 2n.
Hsien-Chih Chang 張顯之
2
I don't think it gives further insights for studying this problem, but the proper scholarly reference for Shallit's talk is: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)
Hermann Gruber
@Hermann: Thank you for the reference, currently I cannot access to the paper, but I will find a way to.
Hsien-Chih Chang 張顯之
I think by using counter we can replace the starter and terminator by a 2-state tiny machine. So this further reduce the size of NFA to 3n+O(1).
Hsien-Chih Chang 張顯之
1
The author's preprint version of the noted JALC paper is here: cs.uwaterloo.ca/~shallit/Papers/re3.pdf The bound, and the proof is the same in the printed version.
Hermann Gruber