stefk0/eai

Записки по „Езици, автомати и изчислимост"

План по ЕАИ ( зима 2018 г. )

1. Увод. Крайни детерминирани автомати. Примери. Конструкции за сечение, обединение, разлика
2. Крайни недетерминирани автомати. Еквивалентност с КДА. Пример за експоненициално покачване на броя на състоянията. Контрукция за конкатенация на автоматни езици
3. Контрукция за звезда на Клини на автоматни езици. Регулярни изрази и езици. Теорема на Клини
4. Лема за покачването. Примери. Релация на Майхил-Нероуд
5. Теорема на Майхил-Нероуд. Метод на Бжозовски
6. Изоморфни автомати. Алгоритъм за минимизация
7. Граматики. Регулярни граматики. Извод в граматика
8. Дървета на извод. Лема за покачването за безконтекстни езици
9. -- няма лекция --
10. Опростяване на граматики
11. Нормална форма на Чомски. CYK алгоритъм
12. Стекови автомати. Теорема за еквивалентност с безконтекстни граматики
13. Детерминистични машини на Тюринг. Разрешими езици. Примери. Многолентови детерминистични машини на Тюринг
14. Недетерминистични машини на Тюринг
15. Кодиране на машини на Тюринг. Примери за неразрешими и неполуразрешими езици. Теорема на Райс

eai's Issues

Лема за покачването и НФЧ

В доказателството на лемата за покачването за контекстно свободни езици се използва нормална форма на Чомски, която е дефинирана по-късно.

Задача 3.34, започнато е упътване, но липсва съдържанието му.

Теорема на Клини

3. Доказателството на теорема 2.1 (Клини) б) подточка -- как стигаме до
   разбиването

L(i,j,k) = L(i,j,k-1) U L(i,k,k-1).(L(k,k,k-1)*).L(k,j,k-1) ?

Задача 3.22

В раздел 3.4 "Недетерминирани стекови автомати", задача 3.22 гласи:

Докажете, че езикът L = {w от {a, b}* | броят на a-тата в w е равен на 2 пъти броя на b-тата в w} не е безконтекстен.

Мисля, че това не е така.

Минимални автомати

В главата 2.5 Минимален автомат. Използвайки релацията на Нероуд и теоремата на Майхил-Нероуд преди дефинирането на едната и доказването на другата, в подглава 2.5.1 идва изневиделица.