Question 1 :  Regular Languages and Automata

Consider the regular expression E = (b | ab)* (a | ε) on alphabet Σ = {a, b} .

(a)  Do the following words match E?  Explain your answer .

(i) ε

(ii)  abba

(iii)  aaa

[6 marks]

(b)  Give a minimal total DFA that recognizes the language described by E and prove

that it is minimal .

[9 marks]

Question 2 : Context-free Languages

Consider the following context-free grammar G on the alphabet Σ = {a . b}

⇒  5   ::=   xx

x   ::=   axa   |  bxb   |  a   |  b   |  e

(a)  Show that the grammar G is ambiguous .                                                   [7 marks]

(b) A student is in the process of transforming G into Chomsky Normal Form and has

reached the following:

⇒  50     ::=     5

5    ::=   xx

x    ::=   Au    |  BV   |  a   |  b   |  e

u    ::=   xA

A    ::=     a

V    ::=   xB

B    ::=     b

The student’s next step is to remove the rule x  ::= e .   Give the grammar that results from this step .

[8 marks]

Question 3 : Turing Machines and Complexity

Consider the following deterministic Turing machine M on alphabet Ω = (a, b,   } .  The tape initially contains a nonempty block of a’s and b’s on an otherwise blank tape with the head on the leftmost character . The transition function is given by the following diagram:

Return True

Right

Read

Right

Read

Read a ,b

Read

Left

(a) Trace the behaviour of the machine M on the word aa .                           [7 marks]

(b)  Recall the notation 艺k(p)=0 xk  for x0 + x1 + . . . + xp .

The processing time for a block of length n > 0 is as follows .

●  In the case where n = 2p+2 (p > 0) the number of steps is (艺k(p)=0 (8k+12))+2 .

●  In the case where n = 2p+1 (p > 0) the number of steps is (艺k(p)=0 (8k +8)) _ 1.

Show that the complexity of M is in O(n2 ) .

[8 marks]