xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写|Assignment代写 - comp2022 Assignment 3

时间：2020-10-18

comp2022 Assignment 3 s2 2020

This assignment is due on Sunday 1st November, 23:59. Submit your code
on Ed. All work must be done individually without consulting someone
else’s solutions in accordance with the University’s “Academic
Dishonesty and Plagiarism” policies. For more details on late penal-
ties, repeated submissions, what to do if you are stuck, etc., see the
Ed Forum post “Assignment Guidelines”.

In this assignment you will implement an algorithm to convert an NFA to a
DFA, and decide if strings are members of the corresponding language,
by performing the following four tasks:

1. Compute the epsilon closure E(q) for each state q ∈ Q of the NFA. 2.
Use the epilson closures to construct an equivalent epsilon-free NFA. 3.
Use the epsilon-free NFA to construct an equivalent DFA.

4. Determine if the input strings are recognised by the DFA.

Input is read from standard input (stdin). The first line of input
indicates which part of the algorithm to execute. The remaining input is
the data to act on. Examples of usage, and of input and expected output
are provided in the appendices.

Skeleton code is provided for Python on Ed. The code demonstrates how to
read the input data. You are not required to use the skeleton code, and
may modify it.

1

• •

2

• •

3

•

• •

Compute epsilon closures of the NFA

Input: epsilon-closure followed by an NFA (the syntax is described in
the appendices). Output: One line per state, giving the epsilon closure
of that state. You can output the lines

(and contents of the sets) in any order. E(q0) = {q0, q2, q3} would be
output as q0:q0,q2,q3 Construct an equivalent epsilon-free NFA

Input: nfa-to-efnfa followed by an NFA and its epsilon closures (the syntax is described in the appendices).

Output: A string representing the equivalent epsilon-free NFA
constructed using the algorithm given in lectures. The states in the new
NFA should have the same names as the corresponding states in the
original one.

Construct an equivalent DFA

Input: efnfa-to-dfa followed by an epsilon-free NFA (the syntax is described in the appen- dices).

Output: A string representing the equivalent DFA, in the format described in the appendices.

Caution: If followed exactly, the algorithm given in lectures will
always result in a DFA with a state for every subset of states of the
given NFA. This exponential growth is highly inefficient, and the test
cases will likely fail because they took too long to compute. To avoid
this “best case exponential” case, you should only construct the states
actually reachable from the start state (i.e. add a state representing
{q0} first, then a state corresponding to each set of states reachable
from that, then the sets reachable from those, etc.), as was
demonstrated in lectures.

1

comp2022 Assignment 3 s2 2020

4

5

• •

Decide if the strings are in the language

Input: compute-dfa followed by a DFA, then one or more strings to test (the syntax is described in the appendices).

Output: For each string, output 1 or 0 only, indicating whether that string was accepted by the DFA.

Submission and Marking

Submit your code on Ed. You do not need to submit anything anywhere else
for this assignment. Each task (1–4) is worth 20 marks. Within each
task, the marks are distributed as follows:

• 5 marks for passing the corresponding test case in appendix 6.3 of
this document. It is permissable to hard-code the solution of this
particular test case in your program (in case your program does not
correctly implement the algorithm).

• 15 marks for passing the remaining test cases, some of which are
hidden, and some of which we will provide the solutions to. It is not
permitted to hard-code the solutions of these cases!

The remaining 20 marks are based on the overall quality of the code. This mark is based on factors such as:

• How readable is the code? e.g. commenting, variable naming, space, line length, etc.

• Are the data structures appropriate to the problem? e.g. how the
automata are represented. • Are the algorithms implemented in a
reasonably efficient way?

• How much of the assignment was attempted.

2

comp2022 Assignment 3 s2 2020 6 Appendices

6.1 Input/output formats

All inputs can be assumed to be well formed (i.e. you do not have to
include error handling for malformed input, and you can assume that
input strings will only include symbols from the input alphabet).

6.1.1 NFA/DFA

A plain text representation of the definition of a finite state automata, as a sequence of lines:

1. The set of states (as a comma separated list) e.g. q0,q1,q2,q3. State names should never

contain ,, :, or whitespace characters.

2. The set of alphabet symbols (as a comma separated list) e.g. 0,1

3. The start state e.g. q0

4. The set of final states (as a comma separated list) e.g. q1,q3

5. A sequence of lines representing transitions, each being a comma
separated list of three values s,c,t denoting a transition from s to t
on symbol c.

• DFA: s,c,t defines δ(s, c) = t. There should be exactly one such line per (state, symbol) pair.

• NFA: s,c,t defines t ∈ δ(s, c). There can be any number of such lines
per (state, symbol) pair. ε is denoted by an empty string (i.e. s„t
defines t ∈ δ(s, ε)).

6. Finally, the word end on a line by itself.

6.1.2 Epsilon Closures

Lines of the form q0:q0,q3,q4, in any order, followed by the word end on
a line by itself. This example denotes E(q0) = {q0, q3, q4}.

6.1.3 Strings to test

• Input: One per line, followed by the word end on a line by itself.

• Output: Just a 1 or a 0 on each line, in the same order that the words were input.

3

comp2022 Assignment 3 s2 2020 6.2 Worked example

This example is included in the test cases on Ed, to help you verify
that you are outputting data in the right format, although it is not
worth any marks. The initial NFA is the one you would get by following
the construction methods shown in class, for the following regular
expression: (a(a ∪ b))⋆

6.2.1 Task 1

If the input is:

epsilon -closure q0,q1,q2,q3,q4,q5,q6,q7 a,b

q0

q0,q4,q6

q0,,q1

q1,a,q2

q2,,q7

q3,a,q4

q4,,q0

q5,b,q6

q6,,q0

q7,,q3

q7,,q5

end

Then the expected output is:

q0:q0,q1

q1:q1 q2:q2,q3,q5,q7 q3:q3 q4:q0,q1,q4 q5:q5 q6:q0,q1,q6 q7:q3,q5,q7

end

nfa-to-efnfa q0,q1,q2,q3,q4,q5,q6,q7 a,b

q0

q0,q4,q6

q0,,q1

q1,a,q2

q2,,q7

q3,a,q4

q4,,q0

q5,b,q6

6.2.2 Task 2

If the input was:

4

comp2022

Assignment 3

s2 2020

q6,,q0

q7,,q3

q7,,q5

end

q0:q0,q1

q1:q1

q2:q2,q3,q5,q7

q3:q3

q4:q0,q1,q4

q5:q5

q6:q0,q1,q6

q7:q3,q5,q7

end

Then the expected output is:

q0,q1,q2,q3,q4,q5,q6,q7 a,b

q0

q0,q4,q6

q0,a,q2 q1,a,q2 q2,a,q4 q2,b,q6 q3,a,q4 q4,a,q2 q5,b,q6 q6,a,q2 q7,a,q4 q7,b,q6

end

A,B,C,D,E a,b

B

B,D,E A,a,A A,b,A B,a,C B,b,A C,a,D C,b,E D,a,C D,b,A E,a,C E,b,A

6.2.3 Task 3

If the input was efnfa-to-dfa, followed by the output of Task 2 (above),
then the expected output DFA follows. Note that the state names do not
need to be the same as these.

5

comp2022 Assignment 3 s2 2020 end

6.2.4 Task 4

If the input was efnfa-to-dfa, followed by the DFA output by Task 3 (above), followed by:

ab

aaaaa abaa ba

end

Then the expected output is:

1 1 0 1

0

Because ab, abaa, and ε are all in the language, but aaaaa and ba are not.

6

comp2022 Assignment 3 s2 2020 6.3 Marked test cases

The tests in this section of the appendix are worth 20% of the overall
grade. You are permitted to solve them by hand, and hard-code their
answers in your program. This will enable you to demonstrate some
understanding of the concepts even if your implementation is incomplete.
You should not hard-code solutions to any of the other test cases.

6.3.1 Input for task 1:

q0,q1,q2,q3 0,1

q0

q1,q3 q0,0,q1 q0,1,q2 q0,,q1 q1,0,q1 q1,0,q2 q2,0,q0 q2,1,q3 q3,,q0 q3,,q2

end

q1 0 0

q2 ε1

ε

q3

q0

ε

ε

ε,0

1

q0

0

6.3.2 Input for task 2:

q0,q1,q2,q3,q4,q5,q6,q7 a,b

q0

q2,q3,q7

q0,,q1

q0,,q3

q1,a,q2

q3,,q4

q4,a,q5

q5,,q6

q6,b,q7

q7,,q4

end

q1:q1 q0:q0,q1,q3,q4 q3:q3,q4 q5:q5,q6

q4:q4 q6:q6 q2:q2 q7:q4,q7

end

q1 aε

q2 q4 a

q5 εε

q6

b q7

q3

7

comp2022

Assignment 3

s2 2020

6.3.3 Input for task 3:

q0,q1,q2,q3 a,b

q0

q1,q3 q0,a,q1 q0,b,q1 q0,b,q2 q1,a,q1 q1,a,q2 q2,a,q0 q2,b,q3 q3,a,q0 q3,a,q2

end

a,b

b

q1 a a

q2 a

q0

a

b

6.3.4 Input for task 4:

The DFA and input strings:

a

q3

error

a,b,c

start

good

error

error

error

start

start

start good,a,error good,b,good good,c,error end

aab

a acaaa abbbb aa

end

,start ,good

,a,error ,b,error ,c,error ,a,good ,b,error ,c,error

a

start

b,c

good b

a,c error

a,b,c

8