Не знаю, зачем Вы стерли регулярки, ну да ладно.
Также мне не очень понятно, почему Вы начали исключать вершину

с 4-я дугами, а не вершину

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

ведь обозначает, что из

в

и в

ведет дуга с меткой

? И откуда она у Вас взялась? В исходном графе есть только пусть

. Может опечатка?
Изучаю алгоритм построения РВ по ДКА, изложенный в книге Хопкрофта. Не уверен, что правильно его понял.
Если я сам правильно помню

, то смысл следующий: у Вас есть граф ДКА, Вы его хотите упростить, уменьшая число вершин. Пусть мы хотим исключить вершину

. Вы ее исключаете, но дуги, ведущие в

и из

надо заменить эквивалентными дугами. Какие это дуги? Ясно, что если есть 2 дуги

(

здесь, есс-но, необязательно различны), и есть петля

, то соответствующую тройку дуг мы должны заменить на дугу

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

. Вот и весь смысл.
Только Вы меня проверьте, могу наврать, а я еще сам себя тоже проверю...
upd: Проверил: так и есть, только афторы еще и меняют 2 разные дуги

и

на дугу

. И есть большая и понятная картинка.