Текст задания

2.1. Для автомата, изображенного на рис. 1, определите, в каком состоянии он будет находиться после исполнения последовательности команд

а) babab;

б) a(bab)n, где n  0.

Рис. 1

2.2. Изобразите в виде схемы автомат, заданный таблицей.

2.3. Среди перечисленных ниже множеств L1, L2, L3, состоящих из слов над двухсимвольным алфавитом {1; 2}, укажите распознаваемые языки. Для каждого из распознаваемых языков постройте распознающий его автомат; для каждого из остальных множеств докажите нераспознаваемость.

а) L1 состоит из всех слов, которые представляют собой нечетные натуральные числа, начинающиеся с цифры 2;

б) L2 состоит из всех слов, у которых первая и последняя цифры различны;

в) L3 состоит из всех слов, количество единиц в которых ровно в два раза больше количества двоек;

Решение

Решение контрольной работы оформлено в виде отчета в Word. Для получения решения необходимо оформить заказ и оплатить его.