3.1 ЗИ — Теория автоматов и шифров

Что делать если при детерминизации автомата, попадаем в состояние из которого по 0 выйти не можем? (в номере 2 в ДЗ по детерминизации) Из {p} по 0 в {q,s}. из {q,s} по 0 в {r}. из {r} по 0 в {s}, из {s} по 0 в пустое множество

@Aleksandr_Volohov Q = 2^{Q’} — в том числе пустое множество там есть.

Т.е это новое состояние, а из состояния пустого множества дуги как проставлять не очень понятно

Новое, конечно, как и все прочие. Проставлять по определению, очевидно. Там все дуги будут в себя.

Т.е попадая, в это множество надо нарисовать петлю, на которой будут все эл множества X для детерминированного автомата?

Да. Это иногда называют мёртвое состояние (dead state) (так в книге Хопкрофта и др. из списка, например). Аналог ситуации stuck в НКА.

Спасибо, тогда сейчас аккуратно перепишу все и отправлю!

Давайте!

Артём Михайлович, в задания по детерминизации есть смысл писать в табличке состояние {} {} {}?И надо ли вообще?

Не знаю, что есть {}{}{}, но {} должно быть, да.

ну вот когда у нас в табличке новой будет, допустим, в 0 {} надо заводить отдельное {} у которого в столбце 0 и в столбце 1 будет {}?

Да, вроде бы.

Ну вы не будете же снижать оценку, если не указать? Не очень понятен вообще смысл этой строчки в таблице

Я уже отвечал на этот вопрос выше, почитайте. Если не будет каких-то состояний, то это неполный ответ.

Хорошо, спасибо)

Артём Михайлович, скажите, пожалуйста, какого типа задания будут на кр? Как в дз?

Да, по стилю — как в ДЗ, но темы могут быть и те, которых не было в ДЗ, но были на лекциях.

Артём Михайлович, во сколько завтра приходить и куда?

В 9:00 в 202.

График распределения оценок за вторую КР.