# Automata 作业 | 编译原理 | Regular Languages | Theories of Computation – School of Computer Science

### School of Computer Science

Automata 作业 | 编译原理 | Regular Languages | Theories of Computation – 这是一个计算理论方面的题目, 考察regular和自动机的理解, 是比较有代表性的计算理论等代写方向

##### Main Summer Examinations 2022
``````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:

###### T
``````ReturnTrue
``````
###### F
``````ReturnFalse
``````
###### 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]
``````