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

Cvičení sedmé

Zásobníkové automaty

1) Daný ZA A = ({q₀, q₁, q₂, q₃, q₄ },{a,b,c,d},{Z,A}, d,q₀,{q₄})

	d(q₀,a,Z) = {(q₀, AZ)}	d(q₀,a,A) = {(q₀, AA)}
	d(q₀,b,A) = {(q₁, epsilon)}	d(q₁,b,A) = {(q₁, epsilon)}
	d(q₁,epsilon,A) = {(q₂, A), (q₃, A)}	d(q₂,c,A) = {(q₂, epsilon)}
	d(q₃,d,A) = {(q₃, epsilon)}	d(q₂,epsilon,Z) = {(q₄, Z)}
	d(q₂,epsilon,Z) = {(q₄, Z)}

Načrtněte stavový diagram ZA A.
Naznačte 4 různé výpočty na vstupu a⁴b²c (stačí na obrázku).
Popište jazyk L(A).

2) Je daný ZA A = ({q₀, q₁, q₂, q₃, q₄ },{a,b,c,d},{X,Y,Z}, d,q₀,{q₂,q₄}), popište jazyk akceptovaný automatem.

	d(q₀,a,Z) = {(q₀, X)}	d(q₀,a,X) = {(q₀, XX),(q₁, YX)}
	d(q₁,a,Y) = {(q₁, YY)}	d(q₁,b,Y) = {(q₂, epsilon)}
	d(q₂,b,Y) = {(q₂, epsilon)}	d(q₂,c,X) = {(q₃, epsilon)}
	d(q₃,c,X) = {(q₃, epsilon)}	d(q₃,d,X) = {(q₄, epsilon)}

3) Konstruujte ZA (akceptující koncovým stavem nebo prázdným zásobníkem) pro jazyky :

L = {aⁱb^j | i<>j, i,j>=0 }
L = {w | w náleží {a,b}^*; w = w^R }
L = {a³ⁿb²ⁿ | n>=1 }
L = {a³ⁿ⁺²b^2n-1 | n>=1 } (DÚ)
L = {w | w náleží {a,b,c}^*; #_a(w) = #_b(w)}
L = {w | w náleží {a,b,c}^*; #_a(w) != #_b(w)} (DÚ)
L = {a^kb^j | 1 <= j <= k <= 2j }
L = {a^n+mb^m+pc^p+n | m,p,n>=1 } (DÚ)
L = {aⁱb^jc^j | i,j>=1 } sjednoceno {a^kb^kc^m | k,m>=1 } (DÚ)
L = {a^k₁ b a^k₂ b ... b a^k_r | r > 1, k_i >= 1 (i = 1, ..., r ; existuje p,s : p <> s, k_p = k_s) } (DÚ)

4) Daný ZA A = ({q₀, q₁ },{a,b}, {Z,A}, q₀, Z, d, {q₁})

	d(q₀,a,Z) = {(q₀, AZ)}
	d(q₀,a,A) = {(q₀, AA)}
	d(q₀,b,A) = {(q₁, epsilon)}

akceptující koncovým stavem transformujte na ekvivalentní automat akceptující prázdným zásobníkem.

DÚ: určete L(A)

5) Daný ZA A = ({q },{(,)}, {Z,L,P}, q, Z, d, 0)

	d(q,(,Z) = {(q, L)}
	d(q,(,L) = {(q, LL)}
	d(q,),L) = {(q, epsilon)}

akceptující prázdným zásobníkem transformujte na ekvivalentní automat akceptující koncovým stavem.

DÚ: určete L(A)

6) Pro danou G navrhněte rozšířený ZA, který provádí syntaktickou analýzu:
- shora dolů
- zdola nahoru

   S => epsilon | abSA
   A => AaB | aB | a
   B => aSS | bA | epsilon