Java程序辅导

1CS1870 Assignment 2
This assignment is mandatory. Solutions should be submitted in PDF format via Moodle by 2pm on
Wednesday 25th March 2020. Everything you submit must be solely your own work.
1.[4 marks] CS1870 Exam 2019
Using only NOT and OR operators, give an expression that is equivalent to the expression
P NAND (Q NAND Q).
2.[7 marks] CS1870 Exam 2019
Write down the logical expression r corresponding to the switching circuit
x
y
z
y
x
x
z
x
1
0
r
3.[10 marks] CS1870 Exam 2019
Draw a canonical pull-up/pull-down switching circuit for the logical expression (x+y) z.
(The inputs may include the negations of the variables x, y and z, but you must not
rewrite the expression.)
4.[8 marks] CS1870 Exam 2018
Decide whether the string aaabababaa belongs to the regular expression
a∗ ( a b a | b )∗( b∗ a ) over the alphabet {a, b}, justifying your answer.
Taking the domain of discourse to be the set of strings defined by the above regular
expression, decide whether the predicate ∀x ∃y ∃z(x = y b z y )
is true or false, justifying your answer.
5.[9 marks] CS1870 Exam 2015
Use Thompson’s construction to construct finite state automaton corresponding to the
regular expression ( q w ( q | u ) ) w∗ over the alphabet {q, u, w}.
..../PTO
26.[9 marks] CS1870 Exam 2017
Use the subset construction to construct a DFA which is equivalent to the following NFA
 



40 53
1
2
a


a

ff

ff
start

* b
a
a
a
j -
j
ff
-
R
Y
ff
ffi
7.[11 marks] CS1870 Exam 2018
Write MIPS code that is equivalent to the following Java fragment
int x = 3 ; for (a0=5; a0>1; a0--) { x = x + 1 ; } ;
8.[9 marks] CS1870 Exam 2018
Give a Push Down Automaton (PDA) which accepts precisely the language
{ ( b a )n bn | n ∈ N} (where the letters are a and b).
Decide whether your PDA is deterministic, justifying your answer.
3Assessment Details And Criteria
This assignment is a madatory part of the course. The questions on the assignment are
not all of the same weight. The marks for each question are shown on the sheet.
To gain all of the marks available for the questions, where appropriate you must also
show how you obtained your answer. Some marks will be given for ‘correct working or
approach’ even when the final answer is not correct. For Question 5 you must give the
NFA exactly as produced by Thompson’s construction.
You should try all the questions and hand in what you have done, even if you are not
able to complete some of the questions. Solutions to the assignment will be discussed in
a lecture slot after the assignments have been marked.
Submission and feedback arrangements
• Solutions must be submitted in PDF format via the links on the course Moodle page.
The submissions must be PDFs not jpeg, Word documents or any other format. You may
hand write and then scan your solutions to obtain a PDF file.
Write your name on every page and make sure the printed version is legible.
The assignment will not be marked if the submission is in the wrong format or not legible.
• In the event of central IT issues at the time of the deadline, inform the course lecturer.
• The assignments will be marked and feedback given.
• General feedback for this assignment will also be posted on the course webpage by 28th
April 2020.
Learning outcomes assessed
The primary purpose of this assignment is formative. It is designed to
 provide a focus for reading and understanding the material on switching network
construction, regular expressions, finite state automata and the MIPS language
 provide practice in using the associated techniques
 provide you with a way of assessing for yourselves the degree to which you have
understood the material.
 qive you some practice with exam style questions
If you do not know how to do a question, begin by reading the corresponding
text in the notes and working through related examples discussed in lectures.
Please feel free to make an appointment to talk to me about things you don’t
understand.