6.2.1 Membership

Every automaton accepts a subset of words over A, i.e. a set of lists with elements in A. A word belongs to that language if the word can reach a final state when starting from a initial state.

q in reach([l1 ... lp])    q in F
-------------------------------------- 
  [l1 ... lp] in Language

The empty word word can reach the initial state.

q in I
------------------------ 
  q in reach(nil)

If a word [l1 ... lp] can reach state and there is a transition then [l1 ... lp l] can reach

(q1,l,q2) in D    q1 in reach([l1 ... lp])      
--------------------------------------------- 
  q2 in reach([l1 ... lp l])

We can easily represent a finite automaton as a record. It is also not difficult to test for membership:

declare Automaton = unit(trans:unit(p:unit(1:[q] 2:nil)
                                    q:unit(1:[p] 2:[q r])
                                    r:unit(1:nil 2:nil))
                         init:[p]
                         fin:[q])
 
fun{Reach Word} %% returns a set of states
   Result = {NewSet}
in 
   if Word == nil
   then 
      for 
         State in Automaton.init
      do 
         {Result.add State}
      end 
   else 
      Prefix#LastLetter = {Split Word}
   in 
      for 
         State1 in {{Reach Prefix}.content}
      do 
         for 
            State in Automaton.trans.State1.LastLetter
         do 
            {Result.add State}
         end 
      end 
   end 
   ResultSet
end 
 
fun{Accept Word}
   {Not {IsEmpty {Intersect {Reach Word} Automaton.fin}}}
end