Задача 26. Две вершины в автоматной диаграмме называются близнецами, если выходящие из них дуги с одинаковыми пометками ведут к одной и той же вершине. По диаграмме D построить эквивалентную ей диаграмму D' так, чтобы в D' не было ни одной пары вершин-близнецов.
Указание. Удалить вершины, недостижимые от начальной, и склеить все склеиваемые вершины в каждой из диаграмм. Если полученные диаграммы совпадают, то исходные были эквивалентны, иначе - нет.
|