Inštrukcie k odovzdávaniu príkladov z AG

r.2007/08 LS

• Popis Vyriešenú úlohu pošlite na moju emailovú adresu (hric AT ktiml ...).
  Do predmetu dajte "AG uloha2z" a pod.
  Mail bude v tele obsahovat platný Prologovský kód, ktorý prejde testom. Nezabudnite '.' na konci. Kod moze obsahovat komentare. Vsetky riesenia/ulohy poslite v jednom maile. (Specifikacia sa može sa zmeniť u ďalších úloh.)
  V súbore ag_ulohy.pl je popis požadovanej štruktúry konečných automatov a testy pre skontrolovanie syntaktickej štruktúry automatu (a celej odovzdávanej úlohy).
  
  
  Testovanie syntaxe ulohy: test1( Uloha/3 ), testovanie suboru: test1f(Filename)
  Volanie testu:
  :- test1(DS).
  DS je datova struktura uloha/3
  1. arg je meno ulohy (uloha1a, uloha1b)
  2. arg je vase meno
  3. arg je popis automatu
  pre ulohu 1(a/b) je to deterministicky konecny automat
  
  
  Príklad (syntakticky správnej) odovzdávanej úlohy obsahujúcej aj popis automatu:
  uloha(uloha1a,'jméno.příjmení',
  ka( % popis det. kon. automatu
  [i1,i2], % stavy
  [a,b], % abeceda
  i1, % poc. stav
  [i1-[a:i2,b:i1],i2-[a:i1,b:i2]], % prech.fce
  [i2])). % konc. stavy
  V prvom parametri termu uloha/3 uvedte meno ulohy (je u zadania), v druhom svoje meno (a pripadne dalsie udaje), v tretom odovzdavane riesenie.
  Dodrzujte platnu prologovsku syntax, napr. apostrofy okolo druheho argumentu. Mozete poslat aj viac (medzi)vysledkov (moze sa zmenit), napr. nedeterministicky automat, potom odvodeny deterministicky a nakoniec redukovany.
  
  (prologovska) datova struktura konecneho deterministickeho automatu:
  ka(stavy, abeceda, init_stav, delta, final_stavy)
  * tvar delta: stav - [pismeno : novyStav]
  * atomy ':' a '-' su definovane ako operatory.
  ** priklad dat.strukt. deterministickeho kon. automatu:
  * ka( %% neparny pocet 'a'
  [i1,i2], % stavy
  [a,b], % abeceda
  i1, % poc. stav
  [i1-[a:i2,b:i1],i2-[a:i1,b:i2]], % prech. fce
  [i2]) % konc. stavy
  
  (prologovska) datova struktura konecneho nedeterministickeho automatu:
  nka(stavy, abeceda, init_stavy, delta, final_stavy)
  * tvar delta: stav - [pismeno : [noveStavy] ]
  ** priklad dat.strukt. deterministickeho kon. automatu:
  * nka( %% neparny pocet 'a'
  [i1,i2,i3], % stavy
  [a,b], % abeceda
  [i1], % poc. stav
  [ i1-[a:[i2],b:[i1]],
  i2-[a:[i1],b:[i2]]
  i3-[a:[],b:[i1,i2,i3]] ], % prech. fce
  [i2]) % konc. stavy
  
  
  Syntax regulárnych výrazov:
  Výraz obsahuje binárne +, unárne *, binarne seq, konstantu lambda a znaky abecedy v zoznamoch.
  Operácie sú definované ako (prologovské) operátory s Nasledujucimi precedenciami. Teda najsilnejsie viaze unarna *, potom seq, a najmenej +
  op(500, yfx, + )
  op(490, xfy, seq )
  op(480, fx, * )
  
  Príklad: R.výraz "a(aba*)*b", tj. a.(a.b.(a*))*.b zapíšeme
  seq([a],seq(*(seq([a,b],*([a]))),[b]), resp. s operatormi
  [a]seq*([a,b]seq*[a])seq[b]
  
  Rozsirena syntax RV:
  RV: (*)/1, +/2, seq/2, empty/0, lambda/0 (=[]), [pismeno/-a]
  specialneRV - rozsirena syntax:
  seqs([RV,..])/1 ... zoznam sekvencii
  ka(KA)/1 ... priame zadanie KA v obvyklej syntaxi (nie NKA)
  compl/1 ... komplement,
  (*)/0, all/0 ... vsetky znaky, nezalezi na abecede, doplni sa
  varovanie: znaky * a / spolu ukoncuju komentar
  intersect/2 = prienik
  (/)/2 = pravy_kvocient (a derivacia)
  (//)/2 = lavy_kvocient - tj. '\' (a derivacia)
  rev/1 = reverzia
  (**)/2 = symetricky rozdiel (diferencia)
  -/2 = nesymetricky rozdiel
  
  

  ---

  Výsledky na webe ag_vysl.txt, prípadne na cvičeniach.

  ---

  r.2007/08 LS

• Úloha 1
  Termín: utorok 25.3.2008
  Navrhnite redukovaný deterministický konečný automat nad abecedou {a,b}, ktorý pozpoznáva nasledujúci jazyk.
  a) pre cvičenie streda 12:20
  V jazyku sú slová, ktoré obsahujú podreťazec "aba" a neobsahujú "baa".
  b) pre cvičenie streda 15:40
  V jazyku sú slová, ktoré obsahujú podreťazec "bba" a neobsahujú "bab".
  

  ---

  Ak nezvládnete redukciu automatu (správne), pošlite (aj) predchadzajuce kroky, tj. neredukovany automat, resp. nedeterministický automat.

  ---

  ---

  r.2006/07 LS

  ---

• Úloha 1
  Termín: pondelok 19.3.2007
  Navrhnite redukovaný deterministický konečný automat nad abecedou {a,b}, ktorý pozpoznáva nasledujúci jazyk.
  a) pre cvičenie streda 12:20
  V jazyku sú slová, ktoré obsahujú podreťazec "aba" a neobsahujú "bab".
  b) pre cvičenie streda 14:00
  V jazyku sú slová, ktoré obsahujú podreťazec "aab" a neobsahujú "bba".
  

  ---

  Ak nezvládnete redukciu automatu (správne), pošlite (aj) predchadzajuce kroky, tj. neredukovany automat, resp. nedeterministický automat.

  ---

• Úloha 2
  Termín: piatok 13.(4.2007)
  Prevedte konečný automat nad abecedou {a,b} na regulárny výraz.
  a) pre cvičenie streda 12:20 (uloha2a)
  ka([i1,i2,i3], [a,b], i1, [i1-[a:i2,b:i3], i2-[a:i3,b:i1], i3-[a:i2,b:i1]], [i2])
  b) pre cvičenie streda 14:00 (uloha2b)
  ka([i1,i2,i3], [a,b], i2, % !nie i1 [i1-[a:i2,b:i3], i2-[a:i3,b:i1], i3-[a:i2,b:i1]], [i3])
  

  ---

• Úloha 3
  Termín: piatok 13.(4.)
  Vyjadrite derivaciu a kvocient ako RV.
  ab) pre cvičenie streda 12:20
  uloha3a: aa \ (a+b)*aabb(a+b)* , tj. lava derivacia
  uloha3b: (a+b)*aabb(a+b)* / b* , tj. pravy kvocient
  cd) pre cvičenie streda 14:00
  uloha3c: (a+b)*aabb(a+b)* / ba , tj. prava derivacia
  uloha3d: (aa)* \ (a+b)*aabb(a+b)* , tj. lavy kvocient
  
  Jadro vyrazu v mojej syntaxi: (*([a]+[b]) seq [a,a,b,b] seq *([a]+[b]))

  ---

  ---