26. Минимизация чистых автоматов.

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

1) Изучить основные понятия теории автоматов (/1/, с. 16-18, /2/, с. 446-455, 477-483, /3/, с. 75-79).

2) Разобрать понятия гомоморфизма, покрытия и эквивалентности автоматов. Доказать теоремы об эквивалентных состояниях (/1/, с. 20-25, /3/, с. 81-87).

3) Проанализировать связь понятий эквивалентного и минимального автоматов. Рассмотреть процедуру построения для данного автомата минимального (/2/, с. 501-508, /3/, 87-90).

Литература, рекомендуемая для изучения темы

1 Плоткин Б.И., Гринглаз Л.Я., Гварамия А.А. Элементы

алгебраической теории автоматов. – М.: Высш. школа, 1994.

2 Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург:

Изд-во Урал. ун-та, 1996.

3 Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир,

1976.