IB102 ­ úkol 7 ­ řešení Odevzdání: 3. 11. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Uvažme operaci symetrický rozdíl (÷) nad jazyky. Pro připomenutí:
L1 ÷ L2 = (L1 L2)  (L2 L1)
a) [1 bod] Je třída regulárních jazyků uzavřena na tuto operaci?
b) [1 bod] Rozhodněte zda platí (rozhodnutí zdůvodněte):
L1 je regulární jazyk, L2 je neregulární jazyk  L1 ÷ L2 je regulární jazyk
a) Nechť L1 a L2 jsou regulární jazyky. Protože třída regulárních jazyků je uzavřená na
rozdíl, tak (L1 L2) i (L2 L1) jsou regulární. Protože třída regulárních jazyků je
uzavřena i na sjednocení, tak (L1 L2)(L2 L1) je také regulární jazyk, tedy L1 ÷L2
je regulární jazyk.
Třída regulárních jazyků je uzavřena na operaci symetrický rozdíl.
b) Tvrzení neplatí. Protipříklad:
Nechť L1 = {} (regulární) a L2 = {an
bn
| n  0} (neregulární). L1 ÷L2 = (L1 L2)
(L2 L1) =   {an
bn
| n > 0} = {an
bn
| n > 0}, což není regulární jazyk.
IB102 ­ úkol 7 ­ řešení Odevzdání: 3. 11. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Najděte bezkontextovou gramatiku G generující jazyk
L(G) = {ai
bj
ck
dl
| i = l  j = k}.
Řešení: Hledaná gramatika je například G = ({S, A, B, C, D, E}, {a, b, c, d}, P, S), kde
P = { S  aSd | aA | Bd,
A  aA | C,
B  Bd | C,
C  bCc | bD | Ec,
D  bD | ,
E  Ec | }
Z neterminálu S se nejprve vygeneruje větná forma ve tvaru ai
Cdl
, kde i = l, buď přes neterminál
A, pokud i > l, nebo B, pokud i < l. Podobně je pak z neterminálu C přes neterminál
D nebo E vygenerováno slovo bj
ck
, j = k.