/* automaty ulohy */
% 11.4.2007
% 19.3.2007

/* 
  (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

 ***
 * testKA(ka)/1
     testTypeKA/1
 * testNKA(ka)/1
 *   testTypeNKA(ka)/1
 * writeKA(ka)/1
 * testTypeRV1/2 [1]+Vyraz, [2]-Chyba
 *
 * simKA(ka,word,out-states)/3 ... krokovanie
 * simNKA(ka,word,out)/3 ... krokovanie
   simNKALamb(ka,word,out-states) % out je 'accept'/'reject'
     eqsimKA(ka1,ka2,maxLength,Abec,'first'/'all')
     eqsimNKA ...
 * 
 * pNKA2KA(NKA,KA)	% prevod NKA(LAmb) na KA 
   pKA2NKA(ka,nka)
 * intersectionKA(ka1,ka2,kaOut)
   unionKA(ka1,ka2,kaOut)
   differenceKA(ka1,ka2,kaOut)
     symDiffKA(ka1,ka2,kaOut)
   complementKA(ka1,kaOut)
   unionNKA(ka1,ka2,kaOut) % pre nedeterministicke
     unionNKA2(ka1,ka2,kaOut) % pre nedeterministicke, s rozroznenim
   %% nie su kvocienty ani derivacie

   redukceKA(KA,kaReduc)
   redukceKAExt(KA,KAReduc, Transf) % transf je pouzite zobrazeni stavu  
     dosazitelneKA(KA, ...)
   redukceKADosaz(KA,KADosazitelne) % len dosaz. stavy

   transformuje stavy KA:
     transformQzKA(MapQ,KA,KA0):-  % MapQ=map([i1-j1,i2-j2]),
   transformuje abecedu z KA
     transformAzKA(MapA,KA,KA0):-  % MapA=map([a-b,b-a]),

   pRV2KA(RV,Abeceda,KA0)
     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

   evalRel(options,Expr,Result)
     relFce
   transform(transf,X,X0,ctx)
 */

/* hlavne volanie testu:
a) test1(DS). 
    DS je datova struktura uloha/3
     1. arg je meno ulohy (uloha1a, uloha1b, uloha2a, uloha2b)
     2. arg je vase meno (a komentar)
     3. arg je popis automatu
       pre ulohu 1(a/b) je to deterministicky (redukovany) 
	konecny automat
       pre ulohu 2(a/b) je to deterministicky konecny automat

a3) test3(DS). 
    DS je datova struktura uloha/3
     1. arg je meno ulohy (uloha1a, uloha1b)
     2. arg je vase meno
     3. arg je popis RV
       pre ulohu 3(abcd) je to (zakladny) regularny vyraz

% uz funkcne
b) test1f(Filename).  
   v subore Filename je datova struktura podla predch. popisu (pripadne opakovane).
  interne:  t93f('ag_uloha2.txt').

c) testTypeRV1/2 [1]+Vyraz, [2]-Chyba

volanie kontroly:
t93a(test). % vypis do suboru

********
** Zadanie:
* Termin ulohy 1: pondelok 19.3.2007
* Termin ulohy 2,3: piatok 13.4.2007
zadania v ag_instr.html

* priklad obsahu mailu:
<begin_of_mail> 
uloha(uloha1a,'jméno.příjmení',
  ka([i1,i2],[a,b],i1,	% popis automatu
    [i1-[a:i2,b:i1],i2-[a:i1,b:i2]],
    [i2])).

<end_of_mail>
*/ 

% :-ensure_loaded('lib_hior').
% :-ensure_loaded('c:/program files/swi_pl/library/lists.pl').

% :-op(500,yfx, + ).
:-op(490,xfy,seq).
:-op(480, fx, * ).

test1(uloha(T,_Name,KA)):-
  MUlohy=[uloha1a, uloha1b, 
	uloha2a, uloha2b, 
	uloha3a, uloha3b, uloha3c, uloha3d],
  rawtest(member(T,MUlohy),
    error(test1_nezname_meno_ulohy,T,MUlohy)),
  testKA(KA).

test3(uloha(T,_Name,RV)):-
  MUlohy=[ uloha3a, uloha3b, uloha3c, uloha3d],
  rawtest(member(T,MUlohy),
    error(test1_nezname_meno_ulohy,T,MUlohy)),
  testTypeRV1(RV,Out),
  write(Out), nl.

test1f(FN):-
  t93f(FN).

t93f(FN):-
  FN='ag_uloha1.txt',
  Op=[],
  t93f_3(Op,FN).

t93f_3(Op,FN):-
  see(FN), 	% 'ag_uloha1.txt'),  
    % tell('ag_res1.txt'), % 'ag_vysl.txt'
  ( t93f_2(Op,1) -> true ; true ),	% kvoli ukonceniu :-)
  seen.
  
t93f_2(Op,N):-	% vlastne citanie
  read(X),
  ( X=end_of_file 
  -> true	% docitane
  ;  rawtest(X=uloha(U,JM,_KA),error(badSyntaxUloha)), % zakladna syntax
     deb(uloha_nacitana,[N,U,JM]),
     !, 
     N1 is N+1,
     t93f_2(Op,N1)
  ).

% test typu RV: Out=yes/no-term_s_chybou
testTypeRV1(RV,Out):-
  (
    ( RV=lambda
    ; RV=empty
    ; RV= *(RV1),
      testTypeRV1(RV1,Out)
    ; RV= RV1+RV2,
      testTypeRV1(RV1,Out1),
      testTypeRV1(RV2,Out2),
      ( Out1 = no-_ 
        -> Out = Out1
        ;  Out = Out2 )
    ; RV=seq(RV1,RV2),
      testTypeRV1(RV1,Out1),
      testTypeRV1(RV2,Out2),
      ( Out1 = no-_ 
        -> Out = Out1
        ;  Out = Out2 )
    ; listOfAtomsNum(RV,1,_,_) 
       % listOfAtoms(RV) % povodne
    ), !,
    ( var(Out) 	% je Out uz dosadene
     -> Out=yes-[]
     ;  true )
  ; Out=no-RV	% najmensi chybny vyraz, dufam
  ) .

% testuje, ci su to atomicke pismena a cisluje ich
listOfAtomsNum(RV1,N1,RV0,N0):-
    RV1=[], RV0=[],
    N0 = N1
  ; RV1=[X|RV2], RV0=[X-N1|RV3],
    N2 is N1+1,
    atomic(X),
    listOfAtomsNum(RV2,N2,RV3,N0) .

% testy typu, verejne
testKA(KA):-
  testKAdl(10,KA).
testKAdl(DLevel,KA):- 
  rawtest(KA=ka(Qs,As,Q0,D,Fs), error(porusena_syntax_KA(ka/5),KA)),
  KA=ka(Qs,As,Q0,D,Fs),
  rawtest(member(Q0,Qs), error('test KA: poc. stav neni ve stavech',Q0,Qs)),
  rawtest(subset(Fs,Qs), error('test KA: konc. stavy nejsou stavy',Fs,Qs)),
  length(Qs,LQs), length(D,LD), length(As,LAs),
  rawtest(LQs=LD, 
    error('test KA: chyba v prech. funkcii-(stav navic?)',D) ),
  forAll(Qs,XQ,
    rawtest(
       (member(XQ-XD,D),
        length(XD,LXD), % length(As,LAs),
        rawtest(LXD=LAs,
          error('test KA: chyba v prech fci-(pism. navic?)',XQ-XD)),
        forAll(As,XA,
          (rawtest(member(XA:XQA,XD), 
             error('test KA: Stav nema prech. fci pro pismeno', 
                    XQ,XQA,XD) )
          ))
      ),
      error('test KA: Stav nema prechodovou funkci',XQ,D))),
  /* ...  */
  rawtestDL(DLevel,11,fail,[testing_KA_ended]).

rawtestDL(DL,MinDL,Test,Message):-
  DL>=MinDL 
    -> rawtest(Test,Message)
    ;  true .
rawtest(Test,Message):-
  call(Test) 
  -> true
  ;  write(Message), nl .

/* pomocne */
writeKA(ka(Q,S,I,D,F)):-
  write('<KA>'), nl,
  write('abec.: '), write(S), nl,
  write('stavy: '), write(Q), nl,
  write('initq: '), write(I), nl,
  write('final: '), write(F), nl,
  write('delta: '), write(D), nl,
  write('</KA>'), nl.
writeKA(nka(Q,S,I,D,F)):-
  write('<NKA>'), nl,
  write('abec.: '), write(S), nl,
  write('stavy: '), write(Q), nl,
  write('initq: '), write(I), nl,
  write('final: '), write(F), nl,
  write('delta: '), write(D), nl,
  write('</NKA>'), nl.

map(_G,[],[]).  %% _G 
map(G,[I|Is],[O|Os]):-
  call(G,I,O),
  map(G,Is,Os).

forAll([],_Var,_Goal).
forAll([X|Xs],Var,Goal):-
  not(not((X=Var,Goal))),
  forAll(Xs,Var,Goal).

filter(_G,[],[]).
filter( G,[I|Is],Os0):-
  ( call(G,I)
  -> Os0=[I|Os1]
  ;  Os0=Os1
  ), 
  filter(G,Is,Os1).

eq(X,X).

uloha(uloha1a,'jméno.příjmení',
  ka([i1,i2],[a,b],i1,	% popis automatu, neparny pocet 'a'
    [i1-[a:i2,b:i1],i2-[a:i1,b:i2]],
    [i2])).

uloha(uloha2,'jméno.příjmení',
  *([a]seq*[b]seq([a,a]+[b,b]))  % (ab*(aa+bb))*
    ).

% koniec testov
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
