FORMÁLNÍ JAZYKY A AUTOMATY I
CVIČENÍ 1.
1. Uspořádejte (podle množinové inkluze) tyto jazyky nad abecedou {a, b}:
L2 L3 u L5 L6
{a,b}* {a}* ■ {b}*
{a,b}* ■ {a} ■ {a,b}*
({a}* •{&})* U ({b}* -{a})*
Své tvrzení odůvodněte!
2. Vyjádřete pomocí jazyků L0 = {0}, L\ = {1} a množinových operací sjednocení, průnik,
komplement vzhledem k {0,1}*, zřetězení, mocnina, kladná iterace a iterace následující jazyky:
a) jazyk X obsahuje všechny slova nad abecedou {0,1}, kterých délka je sudá a současně
obsahují alespoň dva symboly 0 a nanejvýš jeden symbol 1.
b) jazyk Y obsahuje všechny slova nad abecedou {0,1}, které neobsahují tři po sobě
jdoucí stejné symboly a současně začínají a končí stejným symbolem.
3. Rozhodněte a odůvodněte, jestli pro libovolné tři jazyky platí následující rovnosti:
5. Nechť Si = {a,b,c}, S2 = {a, b} a h : S* —> Eí, je homomorfismus daný předpisem: h(a) = aa; h(b) = ba; h(c) = a.
a) Najděte /z-1 (aabaaabaa).
b) Určete h(L), když L = {w £ {a,b}* | tfa(w) =
c) Určete /z_1(£), když L = {w £ {a}* | \w\ = 2fc;fc e N}.
Znakem §x(w) označujeme počet výskytů symbolu x ve slově w.
(Li U L2) ■ L3 = (Lx ■ L3) U (L2 ■ L3) (Lí n L2) ■ L3 = (Li • L3) n (L2 ■ L3)
4. Dokažte nebo vyvraťte následující rovnosti (Li,L2 libovolné jazyky):
(la ■ L2)* ■ Lx = Lx ■ (L2 ■ Lx)* (iiUL2)* =L\-{Ll-L2y
1