Билет 8 (ДКА, алфавит, язык, слова и т.д.)

8. Алфавит, слова, язык. Детерминированный конечный автомат (ДКА). Настроенный автомат. Способы задания. Языки, распознаваемые ДКА. Примеры языков, распознаваемых и нераспознаваемых ДКА. Любой конечный язык распознается конечным автоматом. {a^n b^n | n=0,1,2,…} – не распознается конечным автоматом.