Piata sada domacich uloh

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.

Ulohy 1-3:
Zostrojte konecny automat (vratane delta funkcie) pre nasledovne jazyky dane gramatikami (ak nie je uvedene inak, nad abecedou {a,b}), alebo ak si myslite, ze sa to neda, uvedte dovod.

Uloha 1

Dana je gramatika G = ({S,C,D},{a,b},P,S) s mnozinou pravidiel P:

 S -> aS | baS | aC | D
 C -> bbS | babC | bD
 D -> aaC | bba

Uloha 2

Dana je gramatika G = ({S,C,D},{a,b},P,S) s mnozinou pravidiel P:

 S -> Sba | Da | aC
 C -> abaC | b
 D -> bDb | b

Uloha 3

Dana je gramatika G = ({S},{a,b},P,S) s mnozinou pravidiel P:

 S -> aSb | bSa | epsilon

Uloha 4

Dany je nedeterministicky konecny automat A = ({a,b},K,q₀,delta,F)
F = {q₄ }, K = {q₀, q₁, ..., q₅}

Delta funkcia je dana nasledovne:

 delta(q₀,a) = q₁
 delta(q₀,b) = q₂
 delta(q₁,b) = q₃
 delta(q₂,epsilon) = q₃
 delta(q₃,a) = q₄
 delta(q₄,epsilon) = q₀
 delta(q₄,b) = q₅
 delta(q₅,b) = q₀

Zostrojte deterministicky konecny automat A' taky, ze L(A') = L(A).

Uloha 5

Zostrojte regularnu gramatiku G, ktora generuje jazyk z predchadzajucej ulohy.

Ulohy 6-7:
Zostrojte konecny automat (vratane delta funkcie) pre nasledovne jazyky (ak nie je uvedene inak, nad abecedou {a,b}):

Uloha 6

L = { w | w obsahuje ako podslovo aj 'bab', aj 'abaab' }

Uloha 7

L = { w | w obsahuje podslovo 'baabb' alebo 'bba' a zaroven ma
pocet pismen delitelny tromi }

Uloha 8

Dany je deterministicky konecny automat A. Zostrojte konecny automat A' rozpoznavajuci jazyk

L = { w | w = w₁ abba w₂ abba w₃ ... w_k-1 abba w_k
pre nejake k, pricom w₁w₂...w_k patri do L(A)}

V ulohach 9-10 dokazte, resp. vyvratte tvrdenie, ze L je regularny jazyk. (Hint: Pouzite Myhill-Nerode vetu.)

Uloha 9

        R               *
L = { ww  | w je z {a,b}  }

Uloha 10

                       *
L = { ww | w je z {a,b}  }