Piata sada domacich uloh

Uloha 1

Dana je gramatika G=(N,T,P,S), N={S,A,B,C,D}, T={1,2,3} a
P = { S -> A | BC | D,
      A -> B | C | 1D,
      B -> 1DD | SDS,
      C -> S | 1CB,
      D -> D3 | 2 }
Zostrojte bezkontextovu gramatiku G' taku, ze L(G)=L(G') a G' neobsahuje
chain rules.
Poznamka: Chain rule je pravidlo typu A->B, kde A,B su neterminaly.

Uloha 2

Standardnou konstrukciou prevedte gramatiku G=({S,A,B,C},{a,b,c},P,S)
s mnozinou pravidiel
        P = {S -> aAaAbC | BC | cab; A -> BCaaa; B -> bab; C -> SAcc | b}
do Chomskeho normalneho tvaru.

Uloha 3

Zostrojte deterministicky konecny automat (reprezentujte ho prechodovym 
diagramom, a aj delta funkciou) pre jazyk:
                                         *
  L = { u.ababba.v | u,v su slova z {a,b}  }
  ( . znaci zretazenie slov)

Uloha 4

Zostrojte deterministicky konecny automat (reprezentujte ho prechodovym 
diagramom, a aj delta funkciou) pre jazyk:
                                         
  L = { w | w je cislo v dvojkovej sustave a po deleni 3 dava zvysok 2 }
        w je zapisane obvyklym sposobom, teda najlavejsia cifra je
        najvyznamnejsia. Napr. 110 je 6.

Uloha 5

Zostrojte deterministicky konecny automat (reprezentujte ho prechodovym 
diagramom, a aj delta funkciou) pre jazyk:
                                         
  L = { w | w na abecedou {a,b}, pricom # w = # w (mod 2) }
                                         a     b

Uloha 6

Dana je bezkontextova gramatika G a slovo w z L(G). Najdite dolny odhad na
pocet krokov odvodenia w v G. T.j., najdite co najvacsie cislo Q, vyjadrene
pomocou dlzky w a cislenych charakteristik gramatiky G (napr. pocet pravidiel,
...) take, ze kazde odvodenie w v G ma aspon Q krokov.

Uloha 7