Програмата на курса "Теория на автоматите"
Програмата на курса "Теория на автоматите"
(специалност КН, КБ, 3 семестър, 2010 г.)
- Концепцията за автомат (DFA): черна кутия, алгебра, обозначен диграф. Разпознаване на думи и езици с помощта на DFA. Пълна и непълна ДКА. NFA като алгебра и диграф. Признаване от НКО. Внедряване на изчисления в NFA.
- NCA и DFA: теоремата на Рабин-Скот. Алгоритъм за определяне. Lambda NFA, тяхната DFA еквивалентност и алгоритъм за определяне.
- Еквивалентност на състоянието и еквивалентност на DFA. DFA изоморфизъм. Като се има предвид DFA. Теорема за съществуване, уникалност и минималност за редуциран DFA. Алгоритъм за конструиране на редуциран DFA, доказателство за коректност.
- Операции върху езици. Регулярни езици и регулярни изрази. Теорема на Клийн. Затваряне на клас редовни езици по отношение на допълнение, пресичане, разлика.
- Конструкция на автомат чрез регулярен израз (ламбда-NCA, определяне, минимизиране). Уравнение L=U+LV. Конструиране на регулярен израз от автомат: съставяне на система от линейни уравнения и решаването й по метода на Гаус.
- (Отляво) лични езици. Критерий за редовност по отношение на коефициенти. Връзка между частен и минимален автомат (теорема на Майхил-Нероде). Критерий за редовност от гледна точка на правилни конгруенции.
- Моноид от автоматни преходи. Разпознаване на езици чрез моноиди, критерий за редовност. Синтактичен моноид на език, критерий за редовност.
- Затвореност на класа на регулярните езици по отношение на операциите (обратно, морфизми, разделяне, затваряния по отношение на префикси, суфикси, поддуми), изграждане на съответните автомати. Разрешимост на алгоритмични проблеми за регулярни езици: възникване, празнота, еквивалентност, включване.
- АвтоматичноAho-Korasik за търсене на шаблон и множество шаблони. Функцията за връщане назад и ефективната конструкция на A-K автомата. Приложение на автомата A-K за разпознаване на език с краен антиречник, приложение за компресиране на данни.
- Описателна сложност на обикновените езици. Сложност на операциите: обединение, пресичане, произведение, итерация.
- Синхронизирани автомати. Проверка на синхронизацията. Кубична оценка на дължината на най-кратката дума за синхронизиране. Хипотезата на Черни.
- Крайни автомати и безкрайни думи. Детерминирани и недетерминирани Бучи автомати. Машини Мюлер. ω-регулярни езици, затвореност спрямо операции, характеризиране.
- Автомати с изход. Представяне на разделяне на свободен моноид на регулярни езици чрез автомат с изход. Крайни конвертори, примери. рационална връзка. Теорема на Ниват.
- Клетъчни автомати. Конфигурации. Еволюция. Райските градини, междинни и гранични конфигурации.