Jazyky, automaty a vyčíslitelnost (01JAV)

poslední změna: 21-02-2018

Anotace

Konečné automaty a regulární jazyky, bezkontextové jazyky a zásobníkové automaty, kontextové jazyky a lineárně omezené automaty, jazyky typu 0 a Turingovy stroje. Algoritmy a algoritmicky vyčíslitelné funkce. Rekurzívní funkce, rekurzívní a rekurzívně spočetné množiny. Algoritmicky neřešitelné problémy.

Podrobný sylabus

datum náplň předášky/cvičení
19.2. Základní pojmy z teorie jazyků. Konečný automat, výpočet, jazyk rozeznávaný konečným automatem. Mmožina Rec A*. Uzavřenost na zrcadlový obraz a sjednocení.
20.2. Uzavřenost Rec A* na průnik a levý kvocient. Užitečný stav, trim automat. Prázdnost a nekonečnost jazyka rozeznávaného KA.