21. Рациональные языки.

Рациональные языки были введены С. Клини при изучении языков, распознаваемых автоматами с конечным числом состояний. В контрольной работе необходимо изучить основные свойства конечных автоматов и проанализировать взаимосвязь между рациональными языками и языками, распознаваемыми конечными автоматами. Рекомендуется следующий план работы:

1) Изучить основные понятия теории конечных автоматов (/1/, с. 174-178; /2/, с. 447-453, 483-486).

2) Рассмотреть понятие полугруппы слов и понятие языка, распознаваемого конечным автоматом, исследовать взаимосвязь таких языков с конгруэнциями и фактор-полугруппами полугруппы слов (/1/, с. 178-184; /2/, с. 520-521).

3) Разобрать понятие рационального языка и доказать теорему Клини об эквивалентности этого понятия понятию языка, распознаваемого конечным автоматом (/1/, с. 189-194).

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

1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

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

Изд-во УрГУ, 1996.