Desiata sada domacich uloh

Uloha 1

Zostrojte nedeterministicky a deterministicky polozkovy automat pre jazyk generovany gramatikou G=({S,A,B},{a,b,c,d},P,S), kde

  S -> aAc | aBd
  A -> aAa | b
  B -> aBa | b

Na zaklade toho zistite, ci je tento jazyk LR(0).

Uloha 2

Upravte algoritmus CYK (Cocke, Younger, Kasami) tak, aby nebolo nutne gramatiku upravovat do Chomskeho normalneho tvaru.

Uloha 3

Dokazte, ze k lubovolnemu deterministickemu zasobnikovemu automatu (DPDA) A, ktory docita kazdy vstup, existuje DPDA, ktory akceptuje komplement jazyka L(A).

Uloha 4

Dany je TS A. Zostrojte TS A', ktory simuluje A, pricom predpokladajte, ze A' ma vstupnu pasku zhustenu tak, ze dvojice susednych znakov su na jednom policku. T.j. ak mal A vstup a₁...a_n, predpokldajte, ze vstup A' vyzera: (a₁,a₂)(a₃,a₄)..., abeceda pre A' pozostava zo "zatvorkovanych pismen", posledny znak na paske je bud (a_n-1,a_n), ak n je parne, alebo (a_n,Blank), ak n je neparne.

a) Simulujte automatom A' automat A, tak ze A' vykona rovnako krokov ako by vykonal na tom istom vstupe A. Uvedte detailnu delta-funkciu.
b) Navrhnite simulaciu tak, aby A' urobil radovo polovicu krokov ako by urobil A.

Uloha 5

Dana je gramatika z prednasky G=({S',S,A},{a,b,c},P,S'), kde

   S' -> Sc,   S -> SA | A,   A -> aSb | ab

Simulujte shift & reduce polozkoveho automatu na slove ababaabbc.