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

В этой теме буду публиковать объявления о ДЗ по указанному курсу. Можно задавать вопросы…

Опубликовано первое ДЗ. На его выполнение отводится неделя.

вопрос по нынешнему дз. верно ли я понимаю, что в приведенном отрывке (задание 4) требуется проверять работу автомата на слове из тройки пятиразрядных двоичных чисел? http://take.ms/HqJpB также, не очень ясно, что подразумевается под “другими заключительными конфигурациями” (задание 2). насколько я понимаю, у автомата может быть несколько заключительных конфигураций (например, “закончил работу” и “ошибка”).

У автомата может быть несколько заключительных конфигураций, все они описываются данным в условии определением. Никаких «ошибок» в определении автомата нет.

Можно сказать и так. Хотя для автомата это не тройка слов, а именно одно слово из пяти букв, каждая буква представляет из себя тройку двоичных разрядов.

хорошо, тогда в задании “используя определение отношения ⊢ доказать, что других заключительных конфигураций нет” что именно требуется доказать? отсутствие заключительных конфигураций, не отвечающих общему виду?

Да. Общий вид требуется придумать. А затем доказать, что он соответствует определению.

Самому не верится: опубликовано ДЗ к сегодняшней лекции. Оно связано с проектированием НКАР. С алгоритмом детерминизации мы покончим всё-таки в следующий раз (надеюсь, быстро) и тогда будет ДЗ по нему.

Подскажите, зачем в 4 номере (в новом ДЗ) нужен НКАР, разве что воспользоваться stuck и не рисовать лишних дуг… Нам ведь все равно нельзя запоминать первый входной символ(последнюю цифру числа) и поэтому рисовать 10 дуг.

@Aleksandr_Volohov первую цифру запомнить вполне можно ( понадобится десять состояний), но вы не вполне правильно поняли задание: последней цифрой числа считается крайняя справа. То есть последняя в направлении чтения, а не в направлении увеличения значимости разрядов. Я исправил текст задания, чтобы это было яснее. Если понадобится идея, как строить такой автомат, могу подсказать…

Тогда еще вопрос. В третьем задании чтение тоже слева направо(в признаке делимости на 4 нужны две последние цифры )? Если читать справа, то там красиво получается все

Чтение всегда слева-направо, если не сказано обратное.

Если читать справа, то там совсем не нужен НКАР.

хотелось бы уточнить задание 2. Нам нужно распознавать слова, в которых четное количество 0 или 1 (вроде 00111, 101), либо которые состоят только из четного кол-ва 0 или 1 (0000,11)? Первый вариант пока приводит только к разрастанию моего автомата до почти ДКАР, за исключением первого перехода состояний, описанного в указании.

Первый вариант. Решение должно выглядеть как два маленьких детерминированных автомата проверки чётности (мы писали один такой на позапрошлой лекции), переход в которые происходит по епсилон-дугам вначале.

думаю, теперь мой вариант ближе к истине и дальше от ДКАР. Спасибо!

Есть ли (помимо загрузки файлов в Moodle) другой способ отправить ДЗ?

Еще вопрос. При проектировании автомата мы явно выписываем компоненты и строим таблицу функции перехода. А в Х помимо обычных входных символов мы указываем епсилон или он по умолчанию туда входит для НКАР?

@Evrin епсилон не входит в алфавит, он даже не является символом, но функция переходов НКАР по определению принимает символ алфавита или епсилон. Так что ничего специально писать на эту тему не надо. Только алфавит.

@atsted на данный момент нет. Вы можете попробовать убедить меня, что это негуманный и жестокий способ и предложить свой, но вряд ли у вас это получится.

Опубликовано ДЗ3 (смотреть надо чуть выше, чем элемент с сегодняшней лекцией 6).

Добавлена страница с рекомендованной литературой: на ней я попытался лучше структурировать список из плана курса за прошлый год. Плюс добавились источники по клеточным автоматам.

Давайте поправим срок сдачи ДЗ3?) меня демотивирует, что “Задание просрочено на: 357 дн. 4 час.”

Спасибо, поправил!