Может ли машина Тьюринга решить, принимает ли NFA строку простой длины?

Я хочу знать, разрешима ли следующая проблема:

Экземпляр: NFA A с n государствами

Вопрос: существует ли некоторое простое число p такое, что A принимает некоторую строку длины p.

Я считаю, что эта проблема неразрешима, но я не могу доказать это. Решающий орган может легко иметь алгоритм для определения, является ли конкретное число простым, но я не вижу, как он мог бы проанализировать NFA достаточно подробно, чтобы точно знать, какую длину он может произвести. Он может начать тестирование строк с NFA, но для бесконечного языка он может никогда не остановиться (и, следовательно, не может быть решающим).

Конечно, NFA может быть легко заменен на DFA или регулярное выражение, если это необходимо для решения.

Этот вопрос я обдумываю как подготовительный вопрос к финалу, который я готовлю через 2 недели.

computability finite-automata простуда
источник

Я не уверен, что это уровень студента, так что не беспокойтесь об его удалении. Это может оказаться сложной проблемой, см., Например, terrytao.wordpress.com/2007/05/25/…

Ну, я сделал это, так что это может быть сложно. Я не нашел никаких доказательств неразрешимых проблем, связанных с NFAs / DFA, поэтому я подумал, что было бы интересно попробовать их.

Я полагаю, что вы связаны с другой (более простой) проблемой. Он может ответить «сколько строк длины x принимает NFA?». Используя предоставленную формулу, мы должны были бы проверить бесконечно много экземпляров

чтобы увидеть, существует ли строка, которую NFA принимает, которая проста по длине. Я не спрашиваю о конкретном простом, я спрашиваю о всех из них.

s_{L} (n)

$s_L(n)$

Ответы:

$a + b k$ $\gcd(a, b) = 1$

Объединение вышеупомянутого вместе дает алгоритм, чтобы проверить, содержит ли ваш обычный (или даже контекстно-свободный язык) строки простой длины. Определенно не простой вопрос, ИМВХО ...

vonbrand
источник

Я был бы признателен за помощь в понимании теоремы Париха в этом случае. Очевидно, что мы можем превратить NFA в КПК, просто не используя стек в КПК. Линейные подмножества определяют циклы? Если так, как это работает?

Chill

@Chill, рассмотрим любой путь через DFA. Это может перейти прямо из начального состояния в конечное состояние, или он может зацикливаться. Возможные длины строк определяются «прямой частью» + суммой в раз «длины возможного цикла» для произвольных s. Просто нарисуйте клубок DFA и проследите пути через него. Вы увидите, как возможные длины попадают в семейства арифметических последовательностей, определенных циклами, т. Е. Они образуют полулинейное множество. Не нужно переходить в контекстный контекст (просто хороший бесплатный бонус).

k

$k$

k

$k$

vonbrand

Я думаю, что это отвечает на мой вопрос. Я попытаюсь прочитать больше о теореме Париха. Я понимаю идею этого и как это может определить циклы в этом случае. То, что я хочу выяснить, является более «практическим» решением, где я делаю настоящий алгоритм для решения этой проблемы.

Chill

@Chill, просто посмотри на мой предыдущий комментарий. Не так сложно придумать описание возможных длин, просто стерев символы на DFA в виде графика и проверив переходы между начальным и конечным состояниями. Трудно формализовать, легко понять вручную для каждого конкретного примера.

vonbrand

a a a a (a a)^{*}

$a a a a (a a)^*$