(1)  [6 marks]

Consider the following pushdown automaton M with input alphabet {a, b, #} and stack alphabet {A, B}:

b /B                a A/

a /A

           a A/      q2   

b B/    q3    

b B/

Precisely deine L(M), the language accepted by M . (Assume acceptance by empty stack.)

(2)  [10 marks]

Consider the grammar G  =  ({S, A, B}, {a, b, #}, S, P) where P consists of the following productions:

S → aAS | bBS | #

Aa  →   aA     Ba  →   aB

Ab  →  bA     Bb  →  bB

A#   →   #a    B#   →   #b

(i)  [2 marks] Pick a string of length 5 in L(G) and show its derivation. (ii)  [8 marks] Precisely deine L(G), the language generated by G.

(3)  [20 marks]

Let M be the Turing machine with state set Q = {q0 , . . . ,q7 , ha , hr }, input alphabet   = {a, b, #}, tape alphabet T =  ∪ { , X}, initial state q0 , and the following transition function 6:

#

q1                                 (q2 ,  , R)   (q5 ,  , R)   (q7 , #, R)                 q2                                  (q2 , a, R)    (q2 , b, R)    (q3 , #, R)                 q3                                  (q4 , X, L)                                        (q3 , X, R) q4     (q1 ,  , R)    (q4 , a, L)    (q4 , b, L)    (q4 , #, L)   (q4 , X, L) q5                                  (q5 , a, R)    (q5 , b, R)    (q6 , #, R)                 q6                                                              (q4 , X, L)                      (q6 , X, R)

q7     (ha ,  , S)                                                         (q7 , X, R)

(Remember that unspeciied transitions go to the reject state hr .)

(i)  [8 marks] Draw a transition diagram for M .

(ii)  [6 marks] For each of the following strings, say whether it is accepted by M or not:

–  ab#aa

–  ab#ab

(iii)  [6 marks] Precisely deine L(M), the language accepted by M .

(4)  [10 marks]

This question is about numeric functions. Assume that a natural number n ≥ 0 is represented by the string 1n  (where 10  = ^).

What function fM : N → N does the following Turing machine M compute?

1/X R             1/1 L             1/1 R

q0      / R  q1      / L   q2   X/1 R   q3

(5)  [10 marks]

What partial function fM : {a, b}*  → {a, b}*  does the following Turing machine M compute?

a/a L

b/b L

q2                          q3   

/ S

a

(6)  [6 marks]

Give a countability argument why there are fewer semidecidable  languages than languages that are not semidecidable.

(7)  [14 marks]

Consider the following  nondeterministic  Turing  machine  M with  input alphabet {a, b, c}:

a/a R

b/b R

c/c R

q2        a/a R

b/b R

q5        a/a L 

(i)  [2 marks] What is L(M), the language accepted by M?

(ii)  [5 marks] Give a transition sequence for an input of length 3 containing the maximum number of transitions.

(iii)  [5 marks] Give the function τM , the time complexity of M . (iv)  [2 marks] Give the function sM , the space complexity of M .