1. Алфавит, слова, операции над словами СодержаниеПолугруппа – множество с заданной на нем ассоциативной бинарной операцией.2. Языки. Операции над языкамиL называется усеченной итерацией языка L3. Абстрактные формальные системы4. Формальные порождающие грамматики5. Классификация грамматик6. А-языки. Конечные автоматы. Диаграмма грамматики.Порождение и распознавание цепочек.Лингвистический автоматL(A), допускаемым конечным автоматом A, называется множество допускаемых им цепочек L(A) = { x / (qДетерминизация конечных автоматовA' такой, что L(A')=L(A).Автоматы с - переходами.А = - автомат -переходами. Построим соответствующий детерминированный автомат А’=9. Минимизация числа состояний автомата9.2. Метод Хафмена.Регулярные множества и регулярные выражения.Разрешимые проблемы для А-грамматик7. Нотации для задания КС-грамматик.8. Структура цепочек. СУ-схемыTmt, (mt)Tmt, mt9. Преобразования грамматик.10. Разрешимые и неразрешимые свойства КС-грамматик11. Синтаксический анализ для КС-языковS abccaS abcca12.Элементы теории конечных автоматовКонечный автомат Мура13.Сети автоматов. Их анализ и синтез.
