Занятие 3.1. Минимизация автоматов
Задача 39
КА задан в виде графа.
Построить гомоморфный исходному автомат .
Решение
1. Входной алфавит .
2. Выходной алфавит .
3. Множество состояний .
4. Задаём гомоморфизм.

5. Строим граф.

Задача 40
Получить минимальный автомат для автомата, заданного автоматной таблицей.

Решение
1. Задаём начальное приближение классов эквивалентности. В один и тот же класс включаем такие состояния, у которых для всех входных знаков выходные знаки совпадают. Если задан не полностью определённый автомат, доопределяем его таким образом, чтобы уменьшить число состояний.

2. Пусть получено разбиение на классы эквивалентности. Следующее приближение классов эквивалентности вычисляется так. Два состояния из одного класса эквивалентности относим в один класс на текущем шаге, если для всех входных знаков следующие состояния также принадлежат одному классу, полученному на предыдущем шаге. В противном случае этот класс разделяется на 2 класса таким образом, что эти классы состоят из состояний неотличимых предыдущим разбиением.

3. Повторяем шаг 2 до тех пор, пока разбиение на предыдущем шаге не совпадёт с разбиением на текущем шаге:

4. Так как разбиение на предыдущем шаге совпало с разбиением на текущем шаге, то завершаем процедуру разбиения на классы эквивалентности.
5. Задаём гомоморфизм.
6. Строим минимальный автомат.

Задача 41
КА задан в виде графа.
Построить изоморфный исходному автомат .
Задача 42
Получить минимальный автомат для автомата, заданного автоматной таблицей.

Занятие 3.2 Автомат Мура
Задача 43
Задан автомат Мили в виде автоматной таблицы.

Построить неотличимый от него автомат Мура.
Решение
1. Строим автомат Мура .
a) Входной алфавит .
b) Выходной алфавит .
c) Множество состояний определяем следующим образом: , где , , , , , . Тогда .
d) Строим автоматную таблицу автомата Мура, заполняя её в соответствии с формулами: — неопределенна, , , , где .

2. Минимизируем полученный автомат Мура.
a) Доопределяем состояния с неопределённым выходом таким образом, чтобы уменьшить число состояний: . Задаём начальное приближение классов эквивалентности. В один и тот же класс включаем такие состояния, у которых для всех входных знаков выходные знаки совпадают.

b) Следующее приближение классов эквивалентности вычисляется так. Два состояния из одного класса эквивалентности относим в один класс на текущем шаге, если для всех входных знаков следующие состояния также принадлежат одному классу, полученному на предыдущем шаге. В противном случае этот класс разделяется на 2 класса таким образом, что эти классы состоят из состояний неотличимых предыдущим разбиением.

c) Повторяем шаг b до тех пор, пока разбиение на предыдущем шаге не совпадёт с разбиением на текущем шаге.

d) Так как разбиение на предыдущем шаге совпало с разбиением на текущем шаге, то завершаем процедуру разбиения на классы эквивалентности.
e) Задаём гомоморфизм.

f) Зададим минимальный автомат Мура таблицей.

Занятие 3.3. Детерминация источников
Задача 44
Построить детерминированный КА, распознающий язык , заданный регулярным выражением: .
Решение
1. Строим источник, представляющий язык .

2. Используем синхронную достижимость одним множеством вершин источника другого множества вершин источника для каждого входного знака.
3. Выполняем детерминацию источника.

Считаем полученные множества состояний новыми состояниями детерминированного источника.
4. Строим гомоморфизм, заданный на множествах состояний исходного источника, для получения детерминированного источника.

5. Рисуем детерминированный источник. В полученном источнике заключительными состояниями являются те состояния, в множество вершин которых входит хотя бы одно заключительное состояние исходного источника.