Regular Languages compiler

For this task you need to implement Thompson’s construction for converting a regular expres- sion to an equivalent NFA. Description of Thompson’s construction can be found in Chapter 3 of the textbook and at [login to view URL]’s_construction. 2 Requirements • We make the following assumptions for simplicity. a) The alphabet Σ of the regular expression is always the binary alphabet {0, 1}. b) Regular expressions do not include ∅. c) The empty string ε is represented by e. d) ◦ is represented by . and ∪ by |. e) Regular expressions are represented in postfix notation. f) States of the resulting NFA are numbers. g) For a postfix regular expression R, states introduced by NFA equivalent to a prefix of R are smaller (as numbers) than states introduced by NFA equivalent to longer prefixes of R. For operators (such as concatenation and *) which introduce a start and an accept state, the start state is smaller (as a number) than the accept state. • You should implement a class constructor RegToNFA and a method toString. • RegToNFA takes one parameter which is a string description of a postfix regular expression and constructs the equivalent NFA as per Thompson’s construction. • toString returns a string describing the NFA resulting from Thompson’s construction. A string describing the NFA resulting from Thompson’s construction is of the form N#I#F#Z#O#E. – N is the number of states of the NFA. – I is the initial state. – F is the final state. – Z, O, and E, respectively, represent the 0-transitions, the 1-transitions, and the ε-transitions. 1 – Z, O, and E are semicolon-separated sequences of pairs of states; each pair is a comma-separated sequence of two states. A pair i, j represents a transition from state i to state j; for Z this means that δ(i,0) = j, similarly for O and E. These pairs are sorted by the source state and (if multiple pairs share the same source state, due to non-determinism) then by the destination state. – For example, toString, being invoked on a a RegToNFA object representing the regular expression 01|, should return the string 6#4#5#0,1#2,3#1,5;3,5;4,0;4,2