Конечный автомат Тюринга

[nbyte]

Здравствуйте.
Я хотел-бы спросить по решению следующей задачи

Цитата:

Изобразить конечный автомат Тюринга из следующего языка $A = \{1001,10110,101\}$

Вот такой у меня есть ответ-рисунок

$F=\{q_4,q_7,q_5,q_8\}$

Мне непонятно зачем нужна точка $q_8$?

P.S.
(Если конечно моё решение правильное)

[Xaositect]

$q_8$ здесь только для того, чтобы дуги, которые в нее ведут, куда-то вели.
А вот $F$ у Вас неправильное. У Вас слово $0$ в язык не входит, а приниматься будет.

[Maslov]

$q_8$ - это состояние, в которое автомат попадает, если на вход даётся слово, не принадлежащее языку.

-- Чт ноя 12, 2009 19:47:02 --

И ещё очень важное замечание: в фамилии Тьюринг вторая буква - мягкий знак.

[nbyte]

Цитата:

здесь только для того, чтобы дуги, которые в нее ведут, куда-то вели.

Цитата:

$q_8$ - это состояние, в которое автомат попадает, если на вход даётся слово, не принадлежащее языку.

Спасибо Xaositect, Maslov за помощь. Теперь почти разобрался.

Xaositect, если можно, поясните пожалуйста ещё что вы имели ввиду

Цитата:

А вот $F$ у Вас неправильное. У Вас слово $0$ в язык не входит, а приниматься будет.

Слово $0$?

[Xaositect]

nbyte в сообщении #261389 писал(а):

Слово $0$?

$0$, $01$ и еще бесконечное множество слов, ведущих в $q_8$.
Или $F$ - это не множество принимающих состояний?

[nbyte]

У меня записано, что $F$ - это множество конечных состояний.
Пардон, моя вина, что я сразу это не написал.

[Xaositect]

Вот давайте рассмотрим два слова $1001$ и $1000$.
получив на вход первое слово, автомат закончит работу в $q_4$, а получив второе - в $q_8$. И $q_4$, и $q_8$ входят в $F$, между тем $1001$ входит в $A$, а $1000$ - нет, то есть Ваш автомат должен $1001$ принять, а $1000$ - нет.

[nbyte]

А ну да, так выходит.
Теперь всё ясно. Спасибо вам за помощь.