Трудность найти слово длины не более

Постановка задачи :

Позволять $M$ быть (потенциально недетерминированным) автоматом и $\cal A$быть его входным алфавитом. Есть ли слово$w \in \cal A^*$ улица $|w| \leq k$ что принято $M$ ?

Эта проблема NP-полная? Было ли это изучено? Есть ли алгоритм, позволяющий найти такое слово?

Вычислите пересечение вашего языка CFG с обычным языком $\sum_{i=0}^k A^k$ (это означает умножение количества штатов на $k$и добавление состояния "тупик"). Теперь проверьте, является ли результат пустым: конвертируйте в грамматику (я думаю, что результат будет иметь полиномиальный размер) и «возвратите» от производства epsilon.

Редактировать: Каве упомянул, что это полином в $k$, так что если $k$ в качестве входных данных, алгоритм экспоненциально в $|k|$, Однако Каве нашел способ это исправить. Преобразуйте оригинальный автомат в CFG и замените все терминалы фиксированным терминалом. Теперь используйте итерационный алгоритм, чтобы найти минимальный размер слова, генерируемого каждым нетерминалом, следующим образом.

Инициализируйте все длины с $\infty$и затем итеративно обновлять все длины очевидным способом: с учетом производства $A \rightarrow a^t \prod B_i$ (порядок не имеет значения), положить $f(A) = \min(f(A),t+\sum f(B_i))$, Требование: это сходится в$O(n)$ итерации, где $n$количество нетерминалов. Причина в том, что в дереве, генерирующем слово минимальной длины, нетерминал не используется дважды; для обработки каждого «ребра» требуется не более одной итерации (некоторые ребра могут «обновляться» параллельно).

Измените все символы алфавита на один конкретный символ. Теперь у вас есть КПК, определенный для одного символа. Его язык - это контекстно-свободная грамматика. Тем не менее, контекстно-свободная грамматика над одним символом является регулярной. Итак, конвертируйте CFG в обычный язык, а затем проверьте, содержит ли он слово длины k.

Теперь все эти преобразования требуют экспоненциального времени, но мне кажется маловероятным, что проблема в NP завершена. Особенно если вы позволите полиномиальное время в$k$,

Возможно, я ошибаюсь, и я прошу прощения за мой начальный отрывочный ответ ...

Кстати, тот факт, что CFG над одной буквой является регулярным, следует из теоремы Париха. Хотя прямое доказательство не так уж сложно. Смотрите ссылку для более подробной информации о теореме Париха - это прекрасный результат ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Вероятно, неоптимальный метод: запустить алгоритм Джикстры. Затем для каждого конечного состояния сравните расстояния с$k$, Если есть$\leq k$, прими. Отклонить.

РЕДАКТИРОВАТЬ: вышеупомянутое работает только для NFAs! Прости за это.