[Jprogramming] DFAs

[David Vaughan]

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.

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
​   )

   run 'a'
1
   run 'aa'
0
   run 'aaa'
1
   run 'abbbbbbbbbbbaabbbbb'
1
   run 'abbbbbbbbbbbaabbbbba'
0

I was wondering if anyone knows if it is possible to check if the machine accepts a regular expression (e.g. ab*(aab*)* )?