PFP Homework 1
Jump to navigation
Jump to search
Automatons
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])
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
- Second function runs automaton for given string and establishes, if given input string is accepted by the given automaton. It should work for both deterministic and non-deterministic finite automatons.
isAccepting:: Automaton -> String -> Bool
ghci>isAccepting ex1 "aab"
True
ghci>isAccepting ex2 "aaa"
False
- Finally, create a function that takes a non-deterministic automaton and produces it's deterministic equivalent (the output can be very different based on used methodology).
convert:: Automaton -> Automaton
ghci>convert ex2
(3, "ab", [(0,'a',1), (0,'b',0), (1,'a',1), (1,'b',2), (2,'a',1), (2,'b',0)], 0, [2],)