CA215 Languages and Computability Semester I Repeat Exam 2003/2004 Solutions

CA215 Languages and Computability
Semester I Repeat Exam 2003/2004
Solutions
1. Show whether or not the set of finite length strings over a finite alphabet is countable.
Ans: This set is countable. To show this we assume that there is an alphabetical ordering of the
symbols in the input alphabet. We can then list the strings in lexicographic order:

all the strings of zero length,

then all the strings of length 1 in alphabetical order,

then all the strings of length 2 in alphabetical order, etc.
This implies a bijection between the set of natural numbers and the list of strings, so it is a
countably infinite set.
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).
Ans: (b*ab*a)*b* | (a*ba*ba*)*ba*
3. Construct a deterministic finite-state automaton to recognize the language in Question 2.
Ans:
0
b
1
a
b
b
b
a
2
a
3
3. Consider the following grammar with start symbol S:
S  aSbS
SA
A  aAbA
Ac
Show that this grammar is ambiguous.
Semester 1 Repeat examination 2002-2003
Module Code: CA215
Page 1 of 5
Ans: We show that the grammar is ambiguous by giving two distinct parse trees for the
sentence acbc
S
a
S
S
b
S
A
A
c
c
A
a
A
c
b
A
c
4. 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
Ans: S  aB  aABB  aaBB  aaABBB  aaaBBB  aaabSBB  aaabbABB 
aaabbaBB  aaabbabB  aaabbabb
6. Construct a pushdown automaton that recognises the following language:
{aibjck: i = j+k}
Ans:
states:
input symbols:
stack symbols:
initial state :
final states:
transitions:
{s, q, f}
{a, b}
{a}
s
{f}
{(s, a, ), (s, a),
(s, b, ), (s, ),
(s, c, ), (q, ),
(s, , ), (f, ),
(q, c, a), (q, ),
(q, , ), (f, )}
Semester 1 Repeat examination 2002-2003
Module Code: CA215
Page 2 of 5
7. Consider a Turing machine that has start state 0 and the following transitions:
State Symbol
(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.
Semester 1 Repeat examination 2002-2003
Module Code: CA215
Page 3 of 5
Ans:
(0, #ab####)
|– (1, #ab####)
|– (1, #ab####)
|– (1, #ab####)
|– (2, #ab####)
|– (5, #a#####)
|– (6, #a#b###)
|– (7, #a#bb##)
|– (7, #a#bb##)
|– (2, #a#bb##)
|– (3, ###bb##)
|– (4, ##abb##)
|– (4, ##abb##)
|– (4, ##abb##)
|– (7, ##abba#)
|– (7, ##abba#)
|– (7, ##abba#)
|– (7, ##abba#)
|– (2, ##abba#)
Y: accepts
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)?
Ans: The machine takes an input string of the form #w# and returns an output string of the form
##wwR#
We say that f(n) = O(g(n)) if there are positive constants c and N such that f(n)  cg(n) for all
integers n  N.
The time complexity of the machine is O(n2).
Semester 1 Repeat examination 2002-2003
Module Code: CA215
Page 4 of 5
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?
Ans: This problem is undecidable. To show this is the case, we reduce the problem of whether
or not a Turing machine accepts the empty string (which is known to be undecidable) to it.
Given a Turing machine T, we construct a Turing machine T' which has all the states in T plus
an additional one, called q. T' works by making exactly the same moves as T, except that if T
ever halts, T' moves instead to state q, then halts on the next move. Clearly T accepts the empty
string if and only if T' enters state q.
10. Describe the following problem classes.



P
EXPTIME
NP-complete
Describe the Boolean satisfiability problem. To which of the above classes does it belong (as
far as is known)?
Ans: A problem (language) L is in P if there exists a deterministic Turing machine T that
decides L and runs in time bounded by a polynomial p(n), where n is the length of the input.
A problem (language) L is in EXPTIME if there exists a deterministic Turing machine T that
decides L and runs in time bounded by a exponential 2p(n), where n is the length of the input.
A problem (language) L is NP-complete if L is in NP and every language L in NP is
polynomial-time reducible to L: that is, there exists a polynomial-time computable function f
such that, for every string w, we have w  L iff f(w)  L.
A clique in a graph is a subgraph where every two nodes are connected by an edge. A k-clique
is a clique that contains k nodes.
This problem is in EXPTIME and NP-complete. As far as is known, it does not belong to P,
though this has not been proved.
Semester 1 Repeat examination 2002-2003
Module Code: CA215
Page 5 of 5