Siesta sada domacich uloh

Uloha 1

   (*odovzdavacia uloha)

   Zadefinujte nedeterministicky konecny automat s pruznou hlavou 
   (standardne styri definice).
   Konecny automat s pruznou hlavou ma konecnostavovou riadiacu jednotku,
   jednu vstupnu pasku a citaciu hlavu, ktora moze naraz citat najviac
   k pismen (k je konstanta pre dany automat).

Uloha 2

   Porovnajte triedy jazykov rozpoznavane zariadenim z Ulohy 1 a rozpoznavane 
   nedet. konecnym automatom.

Uloha 3

Je dany konecny automat A=({a,b},K,q0,delta,{q7}), K={q0,q1,q2,q3,q4,q5,q6,q7},
delta funkcia je dana tabulkou:

delta    q0    q1    q2    q3    q4    q5    q6    q7  
  a      q3    q2    q1    q7    q6    q7    q4    q0
  b      q1    q2    q1    q5    q4    q5    q4    q3

Zostrojte deterministicky konecny automat A'=({a,b},K',q0',delta',F') taky,
ze L(A)=L(A') a automat A' splna podmienky:
                                                             *
1. pre kazdy stav q z K' existuje slovo w take, ze (q0',w) |-  (q,epsilon)

2. pre kazdy stav q z K'-{q1'} existuje slovo w take, ze
           *
   (q,w) |-  (qf',epsilon)

3. F'={qf'}

Uloha 4

(*odovzdavacia uloha)
                             *
Je dany jazyk L = { w z {a,b}  | treti znak od konca v slove w je a}.
Zostrojte deterministicky konecny automat A, taky, ze L=L(A).
Nezabudnite uviest dokaz.

Uloha 5

Dokazte, ze ku kazdemu nedeterministickemu konecnemu automatu A existuje
nedeterministicky konecny automat A', ktory ma prave jeden akceptujuci stav
a pritom L(A)=L(A').

Uloha 6

Dany je konecny automat A=({a,b,c},K,q0,delta,{q0,q3})
K = {q0,q1,q2,q3,q4,q5}, delta funkcia je dana tabulkou:

delta    q0     q1     q2     q3    q4    q5
  a      -      -      q1,q5  -     q5    -
  b      q2,q3  -      -      -     -     q3
  c      -      q0,q4  -      q4    -     -
epsilon  -      -      -      q4    q5    q3

Zostrojte konecny automat A' taky, ze L(A')=L(A) a A' neobsahuje
ziaden prechod na epsilon.

Uloha 7

Su dane nedet. konecne automaty A a A'. Zostrojte nedet. konecny automat A''
taky, ze L(A'')=L(A') U L(A).

Uloha 8

Zostrojte det. konecny automat A taky, ze
L(A)={ uabaabv | # uv=0 (mod 3) }
                  b

Uloha 9

Zostrojte nedet. konecny automat A taky, ze
L(A)={ uabaabv | # uv=# uv (mod 2) }
                  a    b