PFP Homework 2
Jump to navigation
Jump to search
Automatons II
Usually, a finite automaton defined as: where Q represents states, next is input alphabet, then transitions (), 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 ; - 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: ; - is a number from interval ;
- 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])
Regular expressions are usually defined recursively as follows:
- Elementary regular expressions are: just symbols or empty string (or empty set but we do not really care about this option).
- We can build new regular expressions from existing one using three basic operations: concatenation, alternation and iteration.
We will accomodate this definition into following data structure:
data RegExpr = Epsilon
| Symbol Char
| Iteration RegExpr
| Concat RegExpr RegExpr
| Alter RegExpr RegExpr deriving (Eq, Show)
As an example we can use following regular expression:
reg1 :: RegExpr
reg1 = Concat (Concat (Iteration (Alter (Symbol 'a') (Symbol 'b'))) (Symbol 'a')) (Symbol 'b')
Your task will be to create a function convert
:
- Function
convert
takes a regular expression and produces an equivalent finite automaton.
convert :: RegExpr -> Automaton
Note: Intermediate steps may require a finite automaton with epsilon steps. Resulting automaton may differ based on used algorithms.
ghci>convert reg1
(3, "ab", [(0,'a',1), (0,'a',0), (0,'b',0), (1,'b',2)], 0, [2])