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
