FORMÁLNÍ JAZYKY A AUTOMATY I
CVIČENÍ 4.
Prosím, odevzdávejte každou úlohu na zvláštním papíře, řádně označeném jménem, skupinou, číslem sady a číslem příkladu.
1. Nechť L je jazyk nad abecedou {a, b} akceptovaný nějakým konečným automatem A =
(K, {a, b}, ô, qo, F). Navrhněte konečný automat akceptující jazyk L
L = Ln{a}{a,b}*{a}
2. Nechť L je jazyk, L C £+, generovaný regulární gramatikou G = (N,T,,P,S). Navrhněte
gramatiku generující jazyk C = {v ■ u \ u, v € S+; u ■ v € L}.
3. Jaký je vztah mezi třídou regulárních jazyků a nejmenší třídou jazyků, obsahující všechny
konečné jazyky a uzavřenou vzhledem k operacím sjednocení, průniku a komplementu?