Задача: Нарисуйте DFA, который принимает слова из алфавита {0,1}, где последний символ больше нигде в слове не повторяется. (пример: слова 0, 1, 00001, 111110, ε есть в языке этого НКА, а слова 010, 111, 0010, 101 — нет).
Я думаю, что я правильно понял DFA, но я не могу минимизировать его, потому что у меня есть состояние ловушки, от которого я не могу избавиться, что бы я ни делал. Любые советы или подсказки?
Ваш DFA верен (за исключением того, что начальное состояние q0 должно приниматься, поскольку пустая строка находится на языке). Он также минимален; мы можем показать, что все наборы строк, которые ведут к каждому состоянию, различимы относительно. язык в соответствии с отношением неразличимости Майхилла-Нероде.
q0: любая строка в L может быть добавлена к строкам, которые ведут сюда (пустая строка), чтобы получить другую строку в L
q1: добавление строки 0 в L к 0 дает 00 не в L, поэтому q1 отличается от q0.
q2: добавление строки 1 в L к 1 дает 11 не в L, поэтому q2 отличается от q0 и от q1 (поскольку добавление 1 к 0 дает 01, который также находится в L)
строки, ведущие к q3, отличаются от q1 тем, что вы не можете добавить пустую строку (т. е. q1 принимает, а q3 — нет), но в остальном идентичны, и поэтому q3 также отличается от q0-q2
строки, ведущие к q4, отличаются от q2 тем, что вы не можете добавить пустую строку (т. е. q2 принимает, а q4 — нет), но в остальном идентичны, и поэтому q4 также отличается от q0-q2
добавление чего-либо, кроме пустой строки, к строкам, ведущим к q5, приводит к строке не на языке, поэтому она отличается от q0-q4
добавление чего-либо к строкам, ведущим к q6, приводит к строке не на языке, поэтому она отличается от q0-q5 (эти строки отличаются от строк, ведущих к q5, только тем, что вы не можете даже добавить к ним пустую строку, чтобы получить строка в L, т. е. q6 не принимает, а q5 принимает).
Поэтому ваш DFA минимален. Вы можете показать это, попытавшись запустить алгоритм минимизации и отметив, что никакие состояния не удаляются.
Примечание: это зависит от ваших определений, но это нормальное (и я бы сказал предпочтительное) определение DFA, что они определяют все переходы, а это означает, что мертвые состояния (или, как вы их называете, ловушки) должны отображаться. Алгоритмы минимизации, вероятно, не удаляют их, но вы можете удалить их, если хотите (хотя я бы назвал получившийся автомат недетерминированным, поскольку для некоторых переходов детерминированное поведение не указано).
