Не детерминированные c Конечные автоматические приемки и отклонения - PullRequest
0 голосов
/ 31 января 2020

Может ли NFA когда-либо принять строку, которой нет в языке? Я знаю, что для принятия NFA строки должен быть хотя бы один способ ее принятия, и мы можем с уверенностью сказать, что NFA принимает ее. Но в случае отклонения ... может иногда случиться так, что если строка, не принадлежащая языку, будет принята NFA?

1 Ответ

0 голосов
/ 31 января 2020

Определение языка , принятого NFA , говорит, что это набор всех строк, принятых NFA. Ясно, что каждая принятая строка принадлежит языку, и поэтому ответ на ваш вопрос таков: Нет.

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

Для недетерминированных c машин Тьюринга существуют такие понятия принятия, как: «принимается более половины вычислений» или «принимается нечетное количество вычислений» ( Паритет ) et c. Там вы можете принимать вычисления, несмотря на глобальный отказ. Но эти понятия широко не используются, и я никогда не видел, чтобы они применялись к конечным автоматам.

...