Совсем простой вопрос возник, но никак не могу построить ДКА для такого языка! Нужно нарисовать схему, или таблицу переходов, или ещё как-нибудь объяснить.

задан 6 Июн '16 19:29

Какой алфавит?

(6 Июн '16 19:39) pavel1076

Алфавит из одного нуля - {0}

(6 Июн '16 19:43) Plutonium

Нашел на http://math.stackexchange.com/questions/752486/dfa-construction-with-three-strings-in-language пример, но там что-то 00 в таблице не распознается!

(6 Июн '16 19:44) Plutonium

@Plutonium дак у Вас проблема с таблицей или с автоматом самим?

(6 Июн '16 19:45) pavel1076

таблица простая, просто переходим из состояния i в i+1, для i<3, для i=3 переходим в i. q1 и q2 заключительные

(6 Июн '16 19:47) pavel1076

Проблема с построением таблицы или графа для такого автомата!

(6 Июн '16 19:48) Plutonium

Спасибо, Паша!

(6 Июн '16 19:52) Plutonium
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
1

Вопрос действительно простой. Берём состояния q0, q1, q2, q3. Стрелки с меткой 0 идут из q0 в q1, из q1 в q2, из q2 в q3, из q3 в q3. Состояние q0 начальное; q1 и q2 заключительные.

ссылка

отвечен 6 Июн '16 19:42

Всё, поняла, спасибо! Я пыталась с одним терминальным состоянием это сделать, вот и не получалось никак)

(6 Июн '16 19:51) Plutonium

@Plutonium: с одним терминальным детерминированного такого автомата в принципе не построить, что достаточно просто доказать. Я думал, трудность была в том, что автомат подразумевался полным -- когда из любой вершины должна выходить стрелка. Если же этого не требовать, то всё ещё проще, так как q3 не нужно. То же самое можно сделать по трафарету для любого конечного множества слов.

(6 Июн '16 20:06) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×54
×36
×27

задан
6 Июн '16 19:29

показан
512 раз

обновлен
6 Июн '16 20:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru