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