PFP Homework 2

Automatons II

Usually, a finite automaton defined as: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (Q, \Sigma, \delta, q_0, F)} where Q represents states, next is input alphabet, then transitions (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q \times \Sigma \rightarrow Q} ), Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle <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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_1 \times a \rightarrow q_2} ;
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_0} is a number from interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle <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])

Regular expressions are usually defined recursively as follows:

• Elementary regular expressions are: just symbols or empty string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} (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])