Условие:
Построить ДКА, допускающий двоичные цепочки, содержащие подцепочку 101.
Найти
Решение:
Для построения ДКА, допускающего двоичные цепочки, содержащие подцепочку 101, можно использовать следующий алгоритм:
Начальное состояние будет обозначено как q0.
Если следующий символ входной цепочки является 0, переходим в состояние q1. Если следующий символ входной цепочки является 1, остаемся в состоянии q0.
Если следующий символ входной цепочки является 1, переходим в состояние q2. Если следующий символ входной цепочки является 0, о...