Теорија алгоритама, аутомата и језика

Циљ и исход предмета

Стицање општих и стручних знања теорије алгоритама, аутомата и језика Студенти ће усвојити важне појмове и знања теорије алгоритама, аутомата и језика – о детерминистичким и недетерминистичким коначним аутоматима, регуларним изразима и регуларним језицима, особинама регуларних језика, контекст-слободним граматикама и језицима, потисним аутоматима, особинама контекст-слободних језика, Тјуринговој машини, одлучивости, класама проблема полиномијалне и експоненцијалне сложености.

Теоријска настава

Алфабет. Стринг и језик над алфабетом. Формалне граматике. Језик дефинисан граматиком. Хијерархија формалних граматика према Чомском. Детерминистички коначни аутомати. Функција прелаза, проширена функција прелаза и језик DKA. Недетерминистички коначни аутомати. Проширена функција прелаза и језик NKA. Еквивалентност DKA и NKA, конструкција методом подскупова. NKA са празним прелазима (ɛ - NKA). ɛ-затворење. Проширена функција прелаза и језик ɛ - NKA. Еквивалентност ɛ - NKA и DKA. Регуларни изрази. Коначни аутомати и регуларни изрази. Еквивалентност регуларних израза и ДКА као формализама. Конструкција регуларног израза на основу датог DKA. Конструкција DKA на основу датог регуларног израза. Примена регуларних израза - лексичка анализа. Регуларни језици. Пумпинг лемма. Еквивалентност и минимизација аутомата. Минимизација DKA. Контекст-слободне граматике. Извођења. Језик дефинисан граматиком. Стабло извођења. Примена контекст–слободних граматика – парсери. Потисни аутомати. Прихватање завршним стањем. Прихватање празним стеком. Еквивалентност контекст- слободних граматика и PA. Детерминистички PA. Особине контекст-слободних језика. Нормална форма Чомског за контекст-слободне граматике. Пумпинг лемма. Тестирање да ли дата реч припада датом контекст-слободном језику. Тјурингова машина. Тјурингова машина са више трака. Недетерминистичка Тјурингова машина. Неодлучивост. Рекурзивно набројиви и рекурзивни језици. Класе проблема P и NP. NP – комплетни проблеми. Доказ NP – комплетности проблема CSAT и 3SAT.

Практична настава

Предавања и вежбе. Предавања се изводе комбиновано. На предавањима се излаже теоријски део градива пропраћен карактеристичним примерима ради лакшег разумевања градива. На вежбама, која прате предавања, раде се карактеристични задаци и продубљује се изложено градиво са предавања. Поред предавања и вежби редовно се одржавају и консултације.