That's a question that involves infinities, on both sides. Any solution to the halting problem would probably be applicable here. But a more practical approach would probably be http://en.wikipedia.org/wiki/DFA_minimization
Here, at least, your one regular expression would correspond to the other after eliminating some state transitions/ -- Raul On Sat, Oct 22, 2011 at 8:04 PM, David Vaughan <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
