School of Computer Science
Automata 作业 | 编译原理 | Regular Languages | Theories of Computation – 这是一个计算理论方面的题目, 考察regular和自动机的理解, 是比较有代表性的计算理论等代写方向
First Year Undergraduate
06-
35393 LC Theories of Computation
Main Summer Examinations 2022
[Answer all questions]
Theories of Computation
Answer ALL questions. The paper will be marked out of 60, which will be rescaled to a mark out of 100.
Exam paper
Question 1 : Regular Languages and Automata
Consider the regular expressionE= (b|ab)(a|) on alphabet ={a,b}.
(a) Do the following words matchE? Explain your answer.
(i)
(ii) abba
(iii)aaa
[6 marks]
(b) Give a minimal total DFA that recognizes the language described byEand prove
that it is minimal.
[9 marks]
35393 LC Theories of Computation
Question 2 : Context-free Languages
Consider the following context-free grammarGon the alphabet ={a,b}
S ::= XX
X ::= aXa | bXb | a | b |
(a) Show that the grammarGis ambiguous. [7 marks]
(b) A student is in the process of transformingGinto Chomsky Normal Form and has
reached the following:
S 0 ::= S
S ::= XX
X ::= AU | BV | a | b |
U ::= XA
A ::= a
V ::= XB
B ::= b
The students next step is to remove the ruleX ::=. Give the grammar that
results from this step.
[8 marks]
Question 3 : Turing Machines and Complexity
Consider the following deterministic Turing machineMon alphabet ={a,b, }. The tape initially contains a nonempty block ofas andbs on an otherwise blank tape with the head on the leftmost character. The transition function is given by the following diagram:
0
T
ReturnTrue
1 2 3
R
4
5
F
ReturnFalse
9
8
L
7 6
Reada,b
Read
Write Right
Reada,b
Right
Read
Left
Read
Left Write Reada,b
Reada,b
Left
Read
Right
(a) Trace the behaviour of the machineMon the wordaa. [7 marks]
(b) Recall the notation
p
k=0xk forx^0 +x^1 ++xp.
The processing time for a block of lengthn >0 is as follows.
- In the case wheren= 2p+2 (p0) the number of steps is (
p
k=0(8k+12))+2.
- In the case wheren= 2p+1 (p0) the number of steps is (
p
k=0(8k+8))1.
Show that the complexity ofMis inO(n^2 ).
[8 marks]
Question 4 : Models of Computation and Decidability
(a) Draw the reduction graph of the following term in-calculus with arithmetic:
(f.y.f(y+ 1))(u. 3 u)
Hereis the multiplication symbol. [7 marks]
(b) A program in java is said to bepurple if it either halts or contains (in the body
code) an even number ofas. Show that purpleness is undecidable.
[8 marks]