10:49 

Вопросы к экзамену по алгебре (3 семестр)

ArtZin
Вопросы к экзамену по алгебре
(3 семестр)

1. Языки и автоматы. Операции с языками. Распознаваемые и нераспознаваемые языки. Замкнутость множества распознаваемых языков относительно объединения, пересечения, взятия прообраза и частных.
2. Полугруппы преобразований. Теорема Кэли. Полугруппа, порожденная множеством.
3. Распознаваемость языка автоматом и моноидом.
4. Детерминированные и недетерминированные автоматы.
5. Замкнутость множества распознаваемых языков относительно произведения и итерации.
6. Рациональные языки. Теорема Клини.
7. Отношение эквивалентности и разбиения. Конгруенции и гомоморфизмы. Факторполугруппа (фактормоноид).
8. Теоремы об изоморфизмах для полугрупп (моноидов).
9. Гомоморфизмы свободного моноида. Синтаксический моноид языка.
10. Минимальный автомат языка.
читать дальше

   

Сообщество имени П.Г.Конторовича™

главная