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 TablePlease 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 ® bSB ® ABB
Give a derivation of the following sentence:
aaabbabb / [10 marks]
Question 6
Construct a pushdown automaton that recognises the followinglanguage:
{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