A8B01DMG - Diskrétní matematika a grafy
Základní pojmy teorie konečných automatů a gramatik: deterministické a nedeterministické konečné automaty, charakterizace třídy jazyků přijímaných konečným automatem a jejich popis regulárním výrazem. Gramatiky a jazyky generované danými gramatikami s důrazem na bezkontextové gramatiky. Vztah bezkontextových gramatik a zásobníkových automatů. Pojem Turingova stroje a seznámení studentů s tím, že existují algoritmicky nerozhodnutelné problémy.