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

Cvičení druhé

Konečné determ. automaty, pumping lemma

1) Popište jazyk akceptovaný KA A = ({q₀, q₁, q₂, q₃},{a,b}, d,q₀,{q₃})

	d(q₀,a) = q₁	d(q₀,b) = q₂
	d(q₁,a) = q₃	d(q₁,b) = q₁
	d(q₂,a) = q₂	d(q₂,b) = q₂
	d(q₃,a) = q₂	d(q₃,b) = q₂

Uveďte jinou formu zápisu automatu. Diskutujte také variantu F = {q₃, q₂}; d(q₃,a) = q₀

2) Konstruujte deterministické KA, které rozpoznávají následující množiny

{a,b,c}⁵.{a,b,c}^*
{w | w náleží {a}^*; |w| = 2k nebo |w| = 7l; k,l>=0 }
{w | w náleží {a,b}^*; #_a(w) = 3k; k>=0 }
{w | w náleží {a,b}^*; w obsahuje podslovo 'abbab' }
{w | w náleží {a,b}^*; w obsahuje podslovo 'ababb' } (DÚ)
{w | w náleží {a,b}^*; w neobsahuje podslovo 'abbab' } (DÚ)
{a,b}^*.({c,d} sjednoceno {d}.{a,b}^*.{c}).{a,b}⁺ (DÚ)
({a} sjednoceno {b}.({a}.{b}^*.{a}).{b})^* (DÚ)

3) Konstruujte deterministické KA pro následující jazyk nad abecedou {a,b,c,d}

L = {a,b}^*{c}{aa,b}^*{d}⁺
L = {w | w náleží {a,b,c}^*, w neobsahuje slovo 'babb'} (DÚ)
L = {a,b}^*.({cd}+{d}{a,b}^*{c}).{a,b}⁺ (DÚ)
a všechny gramatiky z předešlého cvičení (DÚ)

4) Pomocí regulárního výrazu popište jazyk akceptovaný automatem:

5) Co akceptuje následující automat? (#_a(w)=#_b(w) je nedostatečná odpověď)

6) Pomocí věty o vkládání dokažte, že jazyk L není regulární:

L = {aⁱb^j | j>i>=1 }
L = {w | w náleží {a,b}^*; #_a(w) = #_b(w) }
L = { w.w^R | w náleží {a,b}^* }
L = { aⁿ | n = 2ⁱ; i>=0 } (DÚ)