index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení osmé

Uzávěrové vlastnosti CFL

1) O každé z následujících implikací rozhodněte zda je pravdivá

L₁,L₂ bezkontextové => L₁ sjednoceno L₂ je kontextový
L₁ bezkontextový, L₁ průnik L₂ není bezkontextový => L₂ není bezkontextový
L₁ regulární, L₂ bezkontextový => (L₁ průnik L₂)^c bezkontextový
L₁ konečný, L₂ bezkontextový => (L₁ průnik L₂)^c bezkontextový

2) Dané jazyky
L = { ww^R | w náleží {a,b}^*}
R = ( a^*b⁺a)^*
Navrhněte ZA pro jazyk L průnik R

	d_L(q₀,x,Z) = {(q₀, xZ)}	d_R(p₀,a) = p₀
	d_L(q₀,x,y) = {(q₀, xy)}	d_R(p₀,b) = p₁
	d_L(q₀,epsilon,y) = {(q₁, y)}	d_R(p₁,b) = p₁
	d_L(q₁,x,x) = {(q₁, epsilon)}	d_R(p₁,a) = p₀
	d_L(q₁,epsilon,Z) = {(q₂, Z)}
	F_L{q₂}	F_R{p₀}

3) Je dána gramatika S -> aS | Sb | epsilon

Má tato gramatika vlastnost sebevložení?
Je jazyk generovaný gramatikou regulární?
Jaký je vztah mezi vlastností sebevložení a regularitou?

4) Je dán bezkontextový jazyk L, L je podmnožinou {a,b}^*
Zkonstruujeme nový jazyk L₁ takto:
L₁ = { x | existuje y náležící{a,b}^*; xy náležící L}
L₁ = { x | existuje y náležící{a,b}^*; yx náležící L} (DÚ)
Dokažte, že L₁ je taky bezkontextový.