DUBLIN CITY UNIVERSITY

SEMESTER ONE REPEAT EXAMINATIONS 2004

MODULE: CA215

(Title & Code) Languages and Computability

COURSE: B.Sc. in Applied Computational Linguistics

B.Sc. in Computer Applications (IS Stream)

B.Sc. in Computer Applications (SE Stream)

B.Sc. in Computer Applications (Evening)

YEAR: 2

EXAMINERS: Dr. G.W. Hamilton Ext: 5017

(Including telephone Nos.) Mr. Dudley Dolan

Dr. Donncha O’Maidin

TIME ALLOWED: 2 Hours

INSTRUCTIONS: Please answer all 10 questions: All questions carry equal marks

Requirements for this paper / Log Table
Please tick (X) as appropriate / Graph Paper
Attached Answer Sheet
Statistical Tables
Floppy Disk
Actuarial Tables

THE USE OF PROGRAMMABLE OR TEXT STORING CALCULATORS IS EXPRESSLY FORBIDDEN

PLEASE DO NOT TURN OVER THIS PAGE UNTIL YOU ARE INSTRUCTED TO DO SO

Question 1

Show whether or not the set of finite length strings over a finite alphabet is countable. / [10 marks]

Question 2

Write a regular expression which describes the language of all strings from the alphabet {a,b} which either have an even number of a’s or an odd number of b’s (or both). / [10 marks]

Question 3

Construct a deterministic finite-state automaton to recognize the language described in Question 2. / [10 marks]

Question 4

Consider the following grammar with start symbol S:
S ® aSbS
S ® A
A ® aAbA
A ® c
Show that this grammar is ambiguous. / [10 marks]

Question 5

Consider the following grammar with start symbol S:
S ® aB
S ® bA
A ® a
A ® aS
A ® BAA
B ® b
B ® bS
B ® ABB
Give a derivation of the following sentence:
aaabbabb / [10 marks]

Question 6

Construct a pushdown automaton that recognises the following
language:
{aibjck: i = j+k} / [10 marks]

Question 7

Consider a Turing machine that has start state 0 and the following

transitions:
State / Symbol / d(State, Symbol)
0 / # / (1, #, R)
1 / a / (1, a, R)
1 / b / (1, b, R)
1 / # / (2, #, L)
2 / a / (3, #, R)
2 / b / (5, #, R)
2 / # / (2, #, Y)
3 / # / (4, a, R)
4 / a / (4, a, R)
4 / b / (4, b, R)
4 / # / (7, a, L)
5 / # / (6, b, R)
6 / a / (6, a, R)
6 / b / (6, b, R)
6 / # / (7, b, L)
7 / a / (7, a, L)
7 / b / (7, b, L)
7 / # / (2, #, L)
Trace the execution of this Turing machine with the string
#ab####
as input. / [10 marks]

Question 8

Describe in words what the Turing machine in Question 7 does.
What is meant by the statement f(n) = O(g(n))?
What is the time complexity of the machine (in terms of O(f(n)) notation)? / [10 marks]

Question 9

Is the following problem decidable? Give a proof of your answer.
Given a Turing machine M and a state q, will M ever enter state q when run on a blank tape? / [10 marks]

Question 10

Describe the following problem classes:
·  P
·  EXPTIME
·  NP-complete
Describe the problem of finding a clique containing k nodes within a given undirected graph. To which of the above classes does it belong (as far as is known)? / [10 marks]

CA215 Languages and Computability Page 4 of 5