1        (4 marks)

State the five components of the NDFA given below:

a 

b

2        (4 marks)

Draw an NDFA, with alphabet E = {a, b, c}, which accepts the following language: L = {w : there is a symbol ai  e E that does not appear in w}

3        (8 marks)

Using a systematic procedure, convert the following NDFA into an equivalent DFA, and draw the resulting automaton. Show clearly all the steps involved.

4        (4 marks)

Consider the following incomplete application of the Pumping Lemma for regular languages,

is not a regular language:

Assume that L is a regular language. Let n be the number that is given to us by the

Pumping Lemma.

Let w = (01)n+10n. So w e L and its length is clearly greater than n 

So we have a contradiction. Hence L is not a regular language.

Complete this application of the Pumping Lemma by replacing the dots with an argument that leads to the contradiction.

5        (8 marks)

By constructing a tree, identify the distinguishable states for the DFA below. Hence draw a DFA which is equivalent to this one, but which has a minimal number of states. Note that this DFA is complete; you should ensure that your answer is also a complete DFA.

a 

a

a

6        (4 marks)

Write regular expressions to describe each of the following languages:

(a)  [2 marks]     {w e {a, b}* :  w has aab as a substring}

(b)  [2 marks]     {w e {a, b}* :  w does not have aab as a substring}

7        (4 marks)

Derive a regular expression for the language accepted by the following NDFA, showing all your working. [Hint: this NDFA has two accepting states: you should deal with this issue first.]

a 

8        (4 marks)

Consider the following context-free grammar:

S   二   AA I a

A   二   SA I b

Give a derivation to show how the string abbbb can be derived in this grammar.

9        (4 marks)

Give a context-free grammar for the following language:

L = {w e {a, b}* : w contains twice as many as as bs}

10      (4 marks)

Consider the following context-free grammar:

S   二   1S1 I T

T   二   1X1 I X

X   二   0X0 I 1

(a)  [2 marks]    Give a parse tree for the string 00100.

(b)  [2 marks]    Show that the grammar is ambiguous.

11      (8 marks)

(a)  [4 marks]     Draw an NPDA that accepts, by final state, the following language: L = {am bncm+n  : m ≥ 0, n ≥ 0}

(b)  [4 marks]    Give a CFG for the language L from part (a), and draw a parse tree for the string a2 bc3 .

12      (4 marks)

Consider the NPDA below which accepts the following language, by final state:

L = {an bm  : n ≥ 0, m ≥ 0, n  m}

b,a/A 

1

a,a/aa

b,Z/bZ

b,b/bb

a,Z/aZ

(a)  [2 marks]    Give a sequence of IDs to show how the string aab is accepted by the NPDA.

(b)  [2 marks]    Give all possible sequences of IDs which show how the string aabb is

processed by the NPDA, and confirm that they show the string is not accepted. [Hint: there are four possible sequences.]

13      (4 marks)

Convert the following grammar to Greibach normal form:

S   二   ABb I aA I abB

A   二   aA I B

B   二   aAb

14      (8 marks)

Consider the following CFG, and note that it obeys the constraints of Chomsky Normal Form:

S   二   AB

A   二   AA I a

B   二   a I b

Use the CYK algorithm to show:

(a)  [4 marks]    that abb is not in the language generated by the grammar; (b)  [4 marks]    that aaab is in that language.

You should show the full tables constructed as you apply the algorithm.

15      (8 marks)

Use the Pumping Lemma for context-free languages to show that the following language is not

context-free:

L = {0j12j0j  : j ≥ 0}

16      (4 marks)

Consider the following context-sensitive grammar:

(a)  [2 marks]     Define the language generated by the grammar.

(b)  [2 marks]    Give a derivation to show how the string 00110000 can be derived in the

grammar.

17      (4 marks)

Construct a Turing machine (with input alphabet {a, b}) that will accept the following language: L = {w : IwI is a multiple of 3 }

18      (4 marks)

Consider the following Turing machine.

y; y, R

a; a, R

a; a, L

y; y, L

a; x, R   

y; y, R

(a)  [2 marks]    What language is accepted by this TM?

(b)  [2 marks]    Give a sequence of configurations / IDs to show how the machine processes an input of abb.

19      (4 marks)

Explain informally how you would design a 2-tape Turing machine to accept the language

L = {an bncn  : n ≥ 1}.

You do not need to give the full definition of the TM, just an explanation of how you would use the two tapes in the various stages of processing.