Copyright ©2008 T. H. Merrett COMP 617 Information Systems Winter 2008 Week 1 Sequences in Aldat 1. Sequence relations e.g., aababb Str(seq term) 1 a 2 a 3 b 4 a 5 b 6 b 2. Regular expressions e.g., (a|b)*(abb|aa*b) - are recognized by finite automata e.g., DFA( sS term eS ) final( eS) 1 a 125 136 1 b 1 14 125 a 125 125 b 136 136 a 125 136 b 14 14 a 125 14 b 1 relation nextS(eS) <- {(1)}; for k <- 1: [red max of seq] in Str { nextS <- DFA[nextS,Str[k]] }; pr final icomp nextS; NB nextS <- DFA[nextS,Str[k]] means nextS <- DFA[(intg)nextS,(strg)Str[k]] or nextS <- [eS] where sS = [red max of eS] in nextS and term = [red max of term] where seq=k in Str in DFA Instead of for-loop, we could have read-events and event handlers: comp read:Str(nextS) is << Note output parameter >> { k <- 1 + [red max of seq] in .trigger; nextS <- DFA[nextS,Str[k]] } relation nextS(eS) <- {(1)}; nextS <- DFA[nextS,Str[1]] pr term icomp nextS; 3. Deterministic finite automata, DFA, are generated from nondeterministic finite automata, NFA, which can be written down from the regular expression. [e.g., lambda.uta.edu/cse5317/spring01/notes/node9.html] e.g., (a|b)*(abb|aa*b) NFA(sS term eS) final(eS) 1 a 1 4 1 b 1 6 1 a 2 2 b 3 3 b 4 1 a 5 5 a 5 5 b 6 Next steps: regex -> NFA; NFA -> DFA in Aldat. How about DFA -> regex? 4. Query by variables e.g., XXYX applied to aababb will match X=a, Y=b Aldat: term = fun succ of term order seq and term = fun succ of fun succ of fun succ of term order seq order seq order seq and term != fun succ of fun succ of term order seq order seq in the where clause: [seq] where .. in Str Let's introduce succ(n) and pred(n) operators: fun succ(0) of <> order== <> fun succ(1) of <> order == fun succ of <> order fun succ(2) of <> order == fun succ of fun succ of <> order order .. Aldat: term = fun succ(1) of term order seq and term = fun succ(3) of term order seq and term != fun succ(2) of term order seq 5. Can we make an operator for general patterns of this sort? domain X,Y term; << for singleton >> [X,Y] grepseq(seq,term,X,Y;X,X,Y,X) in Str gives (X Y) a b And beyond domain X term; << for singleton >> domain Y(seq,term); << for subsequence >> [X,Y] grepseq(seq,term,X,Y;X,Y,X) in Str gives (X Y ) (seq,term) a 2 a 3 b b 4 a 5 b (all the longest matches).