Non-deterministic Finite Automata

In the seminars, we have encountered Deterministic Finite Automata (DFAs). In this task, we will work with a generalized version of the DFA that is called Non-deterministic Finite Automaton (NFA). NFA is the 5-tuple

• set of states ,
• a finite set of input symbols (called alphabet),
• a set of transitions ,
• a start state ,
• a set of final states .

In other words, NFA is just a directed graph whose vertices are states and transitions are edges labelled by symbols from , i.e., if then there is an edge leading from the state to the state labelled by . We say that NFA accepts a word (i.e., a finite sequence of symbols form ) if there exists a path leading from the start state into a final one labelled consecutively by symbols .

An example of an NFA is depicted in the figure below. This NFA accepts e.g. words or . On the other hand, it accept neither nor .

Example of NFA where , , , and .

Haskell

Your assignment is to implement a function that generates the language accepted by a given NFA. However, since such a language is potentially infinite, the problem is simplified to listing all words of given length that are accepted by the automaton.

For the purpose of this task, the NFA is defined as follows. First, each possible transition is represented as the triplet

data Transition a b = Tr a b a

where the type a represents the states in and b are the symbols ; hence, the transition from the first member of the triplet to the third member of the triplet is possible if and only if the next input symbol is equal to the second member of the triplet. The NFA itself is defined as

data Automaton a b = NFA [Transition a b] a [a]

where the first member is the exhaustive list of transitions, the second member is the start state , and the third is the list of final states . The particular automaton from the figure is defined as follows:

nfa::Automaton Int Char
nfa = NFA [Tr 1 'a' 2,
           Tr 2 'b' 2,
           Tr 1 'a' 3,
           Tr 3 'b' 4,
           Tr 4 'a' 3,
           Tr 2 'a' 4]
           1
           [2,3]

accepts-function

The first part of the task is to decide whether a particular word is accepted by a given automaton. To that end, implement the function

accepts :: (Eq a, Eq b) => Automaton a b -> [b] -> Bool

which takes and automaton and a list of symbols that represents the word, and returns True iff the word is accepted. Notice, a and b are instances of Eq. The function is used as follows.

> accepts nfa "aba"
True

> accepts nfa "abab"
False

Hint: One possibility how to implement the function accepts is to maintain a list of accessible states after consuming an initial segment of the input word.

Consider the NFA from the figure and the word "aba". We start with the list containing the start state [1]. Then we modify this list by the transitions corresponding to the letters as follows:

[1] -a-> [2,3] -b-> [2,4] -a-> [3,4]

Finally, we check if the resulting list of states contains a final state. 3 is a final state, the output is True.

Another example for "abab" is

[1] -a-> [2,3] -b-> [2,4] -a-> [3,4] -b-> [4]

As 4 is not a final state, the ouput is False.

One more example for "ba":

[1] -b-> [] -a-> []

So the output is False.

lwords-function

Next, given the automaton, its alphabet, and a length, generate the list of all words of the given length that are accepted by the automaton. Implement the function

lwords :: (Eq a, Eq b) => [b] -> Automaton a b -> Int -> [[b]]

where the first input is the alphabet as list of unique symbols, the second is the automaton, and the third is the word length. The function returns a list of the accepted words, i.e., a list of lists of symbols. In terms of the task evaluation, the ordering of the words is not relevant. The function operates as follows.

> lwords "ab" nfa 0
[]
> lwords "ab" nfa 1
["a"]
> lwords "ab" nfa 3
["aaa","aba","abb"]

Hint: first, generate all possible words of the given length. Then, filter the words using the function accepts.

Solution

import Control.Monad.State

data Transition a b = Tr a b a deriving Show
data Automaton a b = NFA [(Transition a b)] a [a] deriving Show

--nfa::Automaton Int Char
--nfa = NFA [(Tr 1 'a' 1), (Tr 1 'b' 1), (Tr 1 'c' 1), (Tr 1 'b' 2), (Tr 1 'c' 2)] 1 [2]


walk :: (Eq a, Eq b) => Automaton a b -> a -> [b] -> Bool
walk aut@(NFA trs start finals) state [] | elem state finals = True
                                         | otherwise = False 
walk aut@(NFA trs start finals) state (c:ws) = or [ (walk aut t ws) | tr@(Tr f c' t) <- trs, c' == c, f == state]

accepts :: (Eq a, Eq b) => Automaton a b -> [b] -> Bool
accepts aut@(NFA trs start finals) word = walk aut start word

combinations :: [a] -> Int -> State [[a]] [[a]]
combinations cs 0 = do ws <- get
                       return ws
combinations cs n = do ws <- get
                       let ws' = [ c:w | c <- cs , w <- ws]
                       put ws'
                       combinations cs (n-1)

lwords :: (Eq a, Eq b) => [b] -> Automaton a b -> Int -> [[b]]
lwords abc aut n = reverse $ [ w |  w <- p, accepts aut w] where
    p = evalState (combinations abc n) [[]]

Racket

Implement the functions accepts and lwords. In this task, you may assume that the input word will always be a string. Thus you can use functions string->list and list->string for converting strings to lists of characters and vice versa. Of course, we need to adapt the automaton representation for Racket. First, each possible transition is represented as the triplet:

(struct transition (from-state symbol to-state))

where from-state and to-state are states in and symbol is a symbol in . We can construct the NFA itself as

(struct automaton (trans init-state final-states))

where the first member trans is the exhaustive list of transitions, the second member init-state is the start state , and the third member final-state is the list of final states . The particular automaton from the figure is defined as follows.

(define nfa
  (automaton
   (list (transition 1 #\a 2)
         (transition 2 #\b 2)
         (transition 1 #\a 3)
         (transition 3 #\b 4)
         (transition 4 #\a 3)
         (transition 2 #\a 4))
   1
   (list 2 3)))

Implement the function

(accepts automaton word)

which takes an automaton and a string that represents the word to be parsed by the automaton, and returns #t if the word is accepted, #f otherwise. The function is used as follows:

> (accepts nfa "aba")
#t

> (accepts nfa "abab")
#f

\noindent

Next, given the automaton, its alphabet, and a length, generate the list of all words of the given length that are accepted by the automaton. Implement the function

(lwords alphabet automaton n)

where the first input alphabet is the alphabet passed as a string, the second input automaton is the automaton, and the third input n is the word length. The function returns a list of the accepted words, i.e., a list of lists of characters. In terms of the task evaluation, the ordering of the words is not relevant. The function operates as follows:

> (lwords "ab" nfa 0)
'()

> (lwords "ab" nfa 1)
'("a")

> (lwords "ab" nfa 3)
'("aaa" "aba" "abb")

For testing purposes your file should be named task3.rkt and start with the following lines:

#lang racket

(provide accepts
         lwords)

Solution

#lang racket

(provide accepts
         lwords)

(struct transition (from-state symbol to-state))
(struct automaton (trans init-state final-states))

(define ((s-next fa a) s)
  (define tr (automaton-trans fa))
  (map transition-to-state
       (filter (lambda (t) (and (equal? s (transition-from-state t))
                                (equal? a (transition-symbol t))))
               tr)))

(define ((next fa) a ss)
  (define tr (automaton-trans fa))
  (apply append (map (s-next fa a) ss)))

(define (accepts fa w)
  (define states (foldl (next fa) (list (automaton-init-state fa)) (string->list w)))
  (if (eq? #f (ormap (lambda (s) (member s (automaton-final-states fa))) states))
      #f
      #t))

(define (words alp n)
  (cond
    ((= n 0) '())
    ((= n 1) (map list alp))
    (else (apply append
                 (map (lambda (w)
                        (map (lambda (a) (cons a w)) alp))
                      (words alp (- n 1)))))))

(define (lwords alp nfa n)
  (filter (lambda (w) (accepts nfa (list->string w)))
          (words (string->list alp) n)))


(define nfa
  (automaton
   (list (transition 1 #\a 2)
         (transition 2 #\b 2)
         (transition 1 #\a 3)
         (transition 3 #\b 4)
         (transition 4 #\a 3)
         (transition 2 #\a 4))
   1
   (list 2 3)))


(accepts nfa "aba")
(lwords "ab" nfa 3)