PFP Homework 2

Automatons II

Usually, a finite automaton defined as: $(Q,\Sigma ,\delta ,q_{0},F)$ where Q represents states, next is input alphabet, then transitions ($Q\times \Sigma \rightarrow Q$), $q_{0}$ is starting state and finally there is a set of final states.

In our case, a finite automaton is represented by types:

type Transition = (Int, Char, Int)
type Automaton = (Int, String, [Transition], Int, [Int])

where:

• first number N defines number of states - states will be coded by integer numbers in interval $<0,N)$;
• second element is a string containing the input symbols - you can safely assume; it contains no duplicities;
• third is a list defining the trasition function - elementary transition is a triple (q1, a, q2) representing a transition: $q_{1}\times a\rightarrow q_{2}$;
• $q_{0}$ is a number from interval $<0,N)$;
• finally, there is a list of number representing possible states that are final in defined automaton.

As examples we can use following automatons:

ex1 :: Automaton 
ex1 = (3, "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)], 0, [2],)

ex2 :: Automaton 
ex2 = (3, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])

data RegExpr = Epsilon
             | Symbol Char
             | Iteration RegExpr
             | Concat RegExpr RegExpr
             | Alter RegExpr RegExpr deriving (Eq, Show)

Your task will be to create three functions:

• First function checks if a given finite automaton is a deterministic finite automaton.

isDeterministic:: Automaton  -> Bool

ghci>isDeterministic ex1
True
ghci>isDeterministic ex2
False