Osma sada domacich uloh

Uloha 1

(Odovzdavacia uloha)
Dana je regularna gramatika G=(N,T,P,S), N={S,A,B,C}, T={1,2,3}
    P = { S - 12A | 3C
          A - 2A | 12B | epsilon
          B - 2S | 3A | 1B
          C - 3S | 1A | 2B }
Standardnou konstrukciou zostrojte konecny automat A taky, ze L(A) = L(G).

Uloha 2

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

Standardnou konstrukciou zostrojte regularnu gramatiku G taku, ze L(G)=L(A).

Uloha 3

Pomocou Nerodovej vety dokazte, ze {anbn | n>0} nie je regularny
jazyk.

Uloha 4

Dokazte alebo vyvratte tvrdenie: "Ak deterministicky konecny automat akceptuje viac slov
ako ma stavov, tak akceptuje nekonecne vela slov." 

Uloha 5

Zostrojte (deterministicky alebo nedeterministicky) konecny automat A taky, ze 

L(A) = { w \in {a,b}*   |  w obsahuje dve rovnake podslova dlzky 3 }

Uloha 6

(odovzdavacia uloha)                           
Majme jazyk L = { w \in {a,b}*  |  #a w mod 3 = 1}
Teda neformalne: Jazyk L obsahuje slova, v ktorych pocet a-cok dava po deleni 3 zvysok 1. 

Zostrojte deterministicky konecny automat A, taky ze L=L(A). 
Detailne dokazte, ze L=L(A) (vratane detailnej indukcie pri oboch inkluziach). Slovne
komentare pri dokaze su potrebne, ale "dlhosiahle prozy" bez formalnych detailov budu
hodnotene poctom bodov 0.

Uloha 7

Majme jazyk L = { w \in {a,b}*  |  w neobsahuje podslovo aa }

Popiste (mnozinovou notaciou, pripadne slovne, ale presne) ake slova patria do jednotlivych
tried ekvivalencie Nerodovej ekvivalencie RL.

Uloha 8

Vyuzitim charakterizacie triedy regularnych jazykov pomocou relacii ekvivalencie (teda bez
gramatik a bez automatov) dokazte jej uzavretost na zjednotenie.

Uloha 9

Dokazte, ze trieda bezkontextovych gramatik s pravidlami v N x (NT* U T*) generuje prave
triedu regularnych jazykov.