NFA Acceptance Confusion

Question

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

Например, одна из моих проблем в выполнении домашних заданий выглядят следующим образом:

Дайте НКУ для {ш х ш^R | x ∈ {0, 1} *, w ∈ {0, 1}^2},

где, если я правильно интерпретировал w^R, это обратная строка w, x - некоторая двоичная строка произвольной длины , и w является либо «00», «01», «10», «11».

Таким образом, по существу NFA принимает строку, которая начинается с w, имеет некоторую строку x, а затем заканчивается в обратном порядке w.

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

http://s1056.photobucket.com/user/pcd132/media/Untitled_zps4317347c.jpg.html

Эта NFA принимает почти любую непустую двоичную строку, так же как она удовлетворяет вопрос? Я просто смущен концепцией, если это каким-то образом, каким-то образом примет что-то, оно должно быть принято. Или я должен построить его таким образом, чтобы он каким-то образом принимал условие, но ничего больше? Спасибо за помощь и разъяснение, если я не понимаю этого.

Answer 1

Вы хотите, чтобы NFA принимала все строки на вашем языке и только строки на вашем языке. Одного или другого недостаточно (поскольку NFA для E * достаточно, чтобы получить все строки, а тот, который не принимает ничего, достаточно, чтобы получить только строки).

Существует множество способов создания NFA для этого языка. Один из способов состоит в том, чтобы сначала добавить 7 состояний, которые принимают все 4 двоичные строки длины 2. Каждый из них замыкается на себя либо на 0, либо на 1, чтобы принять любой x, а затем переходит в уникальное состояние таким образом, чтобы начать построение w^Р. Каждое из этих состояний по очереди переходит в принимающее состояние таким образом, чтобы завершить w^R и принимает.