Jazyk a jeho konečná reprezentace Poznámka
Zápisem tta(w) rozumíme počet symbolů a ve slově w. Máme-li např. slovo w = rrsttr, pak J),.(to) = 3.
Příklad 1
Jsou dány dva jazyky Li, L2 nad abecedou {r, s J}*: L1 = {sr, í, rt}, L2 = {rst, s, st}. Vypočítejte:
a) L\ ■ L2
b) L2 • Li
c) (Li • L2) n (L2 • Li)
d) L\
e)
f) L = {i« 6 L\ • L2 j w obsahuje podslovo t s}
g) L = {w € L2 • Li I tfrH = 2}
h) L = {u> e     ; H > 4}
Příklad 2
Jsou dány tři jazyky Li,L2,Z/3 nad abecedou {a, 6, c, <i}*: L\ = {bab, cd, e}, L2 = {ca,cř&, c}, L3 = {a, 6c, dad}.
a) Platí L2 C Li • L2?
b) Platí cacacadba € Lg?
c) Nalezněte všechna slova to G Li • L2 • L3, jejichž délka je přesně 5 (tj. \w\ = 5).
d) Nalezněte všechna slova w G L2 • L3, pro která platí (ja(^) > tlr>(^)-
e) Nalezněte (L± ■
f) Platí (Li • L3)Ä = L.3 • ^1?
1
Příklad 3
Porovnejte následujících 5 jazyků nad abecedou {x, y, z}* z hlediska množinových vztahů C, C, =.
• L1={xY-{y,zY
. L2 = {xY-{y,zY-{xY
• L3 = {x,y,zY
• L4 = {y, zY
• L5 = {xY • {y,zY • {x,yY Příklad 4
Pomocí jazyků L\ = {a}, L2 = {b} a množinových operací U, H, •, iterace (*,+) a doplňku (co-) vyjádřete následující 4 jazyky:
• Li obsahuje slova w taková, že $a{w) > 2.
• L2 obsahuje slova w taková, že \w\ = 2k, k G No
• L3 obsahuje slova w taková, že w = aub, u G {a, 6}*
• L4 obsahuje slova w taková, že řetězec bab je podslovem slova w.
2