IB102 - úkol 4 - řešení
Odevzdání: 18.10. 2010
Vypracoval: James Bond Skupina: MI6
UCO: 007
1. [2 body] Necht' L = [w E [a, b}* | #a(w) je sudý == #a(w) < #b(w)}. Rozhodnete, zda
je jazyk L reguiarní a sve tvrzení dokazte.
(K důkazu regularity jazyka stačí napsat příslušnou gramatiku nebo automat.)
Rešení: Jazyk L není regulární. To dokážeme použitím Pumping lemmatu.
• Mejme libovolne n, nadále pevne.
• Zvolíme si slovo w E L tak, že |w| > n:
• Vsechna mozna rozdelení slova w = xyz,      < n, y = e vypadají takto:
x = b    y = b z
b2n+\-k-l a2n
(k > 0,l> 0,k + l < n)
• Zvolíme si i = 0. Potom platí:
xylz = bk (bl)0b
b2n+1-1 a2n
Zrejme b2n+1 la2n E L, protože počet symbolU a v tomto slove je sudý a počet b je mensí nebo roven počtu a, díky tomu že l > 0. Podle PL tedy L není regularní. □
IB102 - úkol 4 - řešení
Odevzdání: 18.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Mejme gramatiku G = ({S,X,Y}, {a,b,c},P,S), kde
P = {      S  — XY,
Y  —  aYa | bYb | c, Xab  - baX, Xc  —  e }
Popise jazyk generovaný gramatikou G a urCete, zda je tento jazyk regulární. Sve tvrzení dokažte.
Rešeni: Jazyk generovaný gramatikou G je {baba}*. Tento jazyk je regularní, je pro nej napr. mozno sestrojit nasledující koneCný automat.
Q1
q3
Q2
b
a
a
b