Конечные автоматы и регулярные языки. Лекция 13

1. Конечные автоматы и регулярные языки Лекция 13

§7. Минимизация конечных автоматов.

2. §7. Минимизация конечных автоматов.

Поставим такой вопрос: нельзя ли для произвольного конечного
автомата построить эквивалентный конечный автомат с меньшим
числом состояний?
Оказывается, что ответ на этот вопрос положителен.
Более того, можно построить конечный автомат, эквивалентный
исходному и имеющий наименьшее число состояний (среди всех
конечных автоматов, эквивалентных ему).
Процедуру построения такого автомата называют минимизацией
конечного автомата.

3. §7. Минимизация конечных автоматов.

В силу теоремы о детерминизации (см. теорему 5) можно
считать, что исходный конечный автомат