Thompson’s construction Compiler project

Đã Đóng Đã đăng vào 2 năm trước Thanh toán khi bàn giao
Đã Đóng 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

Java

ID dự án: #33245667

Về dự án

7 đề xuất Dự án từ xa 1 năm trước đang mở

7 freelancer chào giá trung bình$89 cho công việc này

Muhammadsamran

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

$20 USD trong 7 ngày
(36 Nhận xét)
5.8
HafizShahan

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

$100 USD trong 7 ngày
(26 Nhận xét)
5.2
JawadIT

Hi there. I am a Java Developer and Expert since 10+ years and developed 500+ java applications, algorithms and system designs. I have portfolios in Compiler Constructions, Algorithm Development and Implementations a Thêm

$10 USD trong 1 ngày
(34 Nhận xét)
5.1
theatasolution1

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

$20 USD trong 1 ngày
(19 Nhận xét)
4.3
Nilushika

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.

$150 USD trong 7 ngày
(0 Nhận xét)
0.0