I think you misunderstood my question. What I meant was, could I feed in that regexp and be told whether it correctly describes the DFA? Equally, how could the regexp be calculated algorithmically?
___________________________ David Vaughan On 22 Oct 2011, at 14:50, Raul Miller <[email protected]> wrote: > On Sat, Oct 22, 2011 at 5:43 AM, David Vaughan > <[email protected]> wrote: >> I wrote a script to model the behaviour of Deterministic Finite Automata, >> defined as the DFA, M = (Q,L,delta,s,F), where Q is the set of states, L is >> the alphabet, delta is the transition function, delta: Q x L -> Q, s is the >> start state, F is the set of all accept/final states. > > This sounds like the sort of thing I use dyadic ;: for. > >> There is a verb, run, which takes a string and returns 1 if the string is >> accepted by the machine, 0 if not. >> >> M =: 0 1 2 ; 'ab' ; (1 2 ; 0 1 ; 2 0) ; 0 ; 1 2 NB. M=(Q,L,delta,s,F) >> >> Q =: >0{M NB. states >> L =: >1{M NB. language >> delta =: >2{M NB. transition >> function >> s =: >3{M NB. start state >> F =: >4{M NB. final states >> >> run =: 3 :0 NB. run y tests if y >> is accepted >> q =. s >> while. 0<#y do. >> q =. (L i.{.y) { >q{delta >> y =. }.y >> end. >> q e. F >> ) > ... >> I was wondering if anyone knows if it is possible to check if the machine >> accepts a regular expression (e.g. ab*(aab*)* )? > > So, you have a machine that processes lists of 'a's and 'b's. And, by > the way, even if I was not using dyadic ;: I would have written it > differently: > > RUN=: 1 :0 > 'Q L D S F'=. >L:_1 m > assert ($D) -: Q ,&$ L > F e.~ ({ {&D)/S,L i.|.y > ) > > run=: M RUN > > So, anyways, you have three state transitions: > > 0: initial state, or an 'a' from state 1, or a 'b' from state 2 > 1: after receving an 'a' from initial state > 2: after receving a 'b' from initial state > > States 1 and 2 hold until they receive their respective character. > > And the result is true if it's in state 1 or 2 when it reaches the end > of the stream. > > So, translating those rules to the language of regular expressions, I get: > > (ab*a|ba*b)*(aa*|bb*) > > The first part of this regular expression is everything that it > accepts which brings it back to the initial state. The remainder are > the sequences which it accepts to get from that state to an acceptable > state without bringing it back to the initial state. > > And when I contrast this to your ab*(aab*)*) so your regular > expression does not accept a stream which starts with a 'b', so we > know it accepts a smaller set of sequences than your machine. > Continuing on, I see that after ab* your machine will be in an accept > state, and your trailing (aab*)* will take it back to state 0 and then > out again an arbitrary number of times. > > So, yes, your machine would accept the same sequences that your > regular expression would accept (and others as well). > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
