Thompson’s construction Compiler project
$10-30 USD
Thanh toán khi bàn giao
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
ID dự án: #33245667
Về dự án
7 freelancer chào giá trung bình$89 cho công việc này
Hello Sir/ Ma’am A skilled full stack developer, I have rich experience in JAVA,C, C++, C#, Python, .NET , MYSQL, SQL, IONIC , MATLAB,PHP and ARDUINO. I am very confident with my skills and I'd like to help your bu Thêm
Hi, I'm working as core java engineer from past 6 years and have implemented Turing machine algorithms multiple times in Java, let's jump on chat to discuss about the project in detail
Hello, I'm an expert Java developer with experience in object-oriented, data structure, swing, JavaFX and more advanced. I can help you to finish this project with great quality. We can negotiate on price/Budget Regard Thêm
hi, Im 10 year experienced Java developer. and I did computer engineering, so familiar with this type of algorithoms. I have many experiences implementing this king of algorithoms.