/* 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: 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])). */ % :-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(''), 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(''), nl. writeKA(nka(Q,S,I,D,F)):- write(''), 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(''), 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%