SULIT
Faculty o f
Computing
UNIVERSITITEKNOLOGI MALAYSIA
FINAL EXAMINATION SEMESTER 1 , 2017 / 2018
SUBJECT CODE : SCSJ3203
SUBJECT NAME : THEORY OF COMPUTER SCIENCE
SECTION : ALL
TIME : 9.00 AM -12.00 NOON
DATE/DAY : 03 / 01/2018 (WEDNESDAY)
VENUES DEWAN SERBAGUNA KTDI
INSTRUCTIONS:
ANSWER ALL 10 QUESTIONS IN THE QUESTION BOOKLET. THE MARKS FOR
EACH QUESTION IS AS INDICATED.
(Please Write Your Lecture Name And Section In Your Answer Booklet)
Name
I/C No.
Year/Course
Section
Lecturer Name
This questions paper consists of ELEVEN ( 1 1) printed pages including this page.
STRUCTURED QUESTIONS [100 marks]
Answer all the questions.
Question 1 [10 marks]
Generate the context free grammar, C F G (that is not regular grammar) according to each
following language, L(G) or regular expression.
(a) 0 (0+ 1) *1 [2 marks]
(b) ((0+ 1) ( 0 + 1))* [2 marks]
(c) a(a+b)*b+b(a+b)*a [3 marks]
(d) anbncm n,m>0 [3 marks]
2
Question 2 [10 marks]
Let G be the grammar
S -* A B C
A —*■aA | a
B — *■ abB | bbB \k
C bC\X
(a) Give a leftmost derivation of string aa b abbb [2 marks]
(b) Give a rightmost derivation of string abb a ba b b [2 marks]
(c) Build the derivation tree for the derivation in parts (a) and (b) [4 marks]
(d) Give a regular expression for L(G) [2 marks]
3
Question 3 [10 marks]
Generate the Regular grammar (RG) according to the each following context free grammar
(CFG).
a) S —>aBa [2 marks]
B —>bB I A,
b) S —» AB [2 marks]
A —>aA | X
B -* bB I X
c) S —*AS [2 marks]
A —>ab
d) S —>aA [2 marks]
A —>aA I bA I X
e) S -> AaaA [2 marks]
A —►aA | bA | X
4
Question 4 [10 marks]
Generate the regular grammar according to the each following regular expression,
a) b*ab*ab*a [2 marks]
b) a*b(bb)*aa* [3 marks]
c) (a*ab*)* [2 marks]
d) (aa*(ab+a)*) [3 marks]
Question 5 [10 marks]
Let M be the PDA defined as follows
M: Q = {qo, qu qi} 8(^0, a,X) = {[?o, A]}
2 = {a, b, c} 8(0o, b, k) = {[0i, >,]}
r={X} 8(0i, b, k) = {[0i, X,]}
F= {qz} 8 (01, c,X) = {[02, X]}
8(02,C ,A )={[02,X ]}
a) Give a state diagram of M. [2 Marks]
b) Trace the computation in M that accepts aabbc. [2 Marks]
c) Write a set notation to define the language L(M). [3 Marks]
d) Construct a grammar G that accepts L(M). [3 Marks]
Question 6 [10 marks]
Construct the PDA for each of the following languages:
a) U = {dnb2mcn | m, n > 0} [5 marks]
r b) L2 = {anbmc2mcT \ n > 0 , m > 0 } [5 marks]
Question 7 [10 marks]
Let M be the Turing Machine defined by
5 B a b c
qo <}2> R
qi qi, c, l qi, b, L
qz qi, B, L qi, a, R q2, c, R q2, c, R
(a) Trace the computation for the input string aabca. [2 marks]
7
(b) Trace the computation for the input string bcbc. [2 marks]
(c) Give the state diagram of M. [4 marks]
(d) Describe the result of a computation in M. [2 marks]
Question 8 [10 marks]
Design a Turing Machine for the following questions,
(a) Design a Turing Machine for odd number of “1” [3 marks]
(b) Design a Turing Machine that accepts even-even language [4 marks]
(c) Design a Turing Machine to recognize all strings in which ‘010’ is present as substring
[3 marks]
9
Question 9 [10 marks]
Given the following language :
L(M) = {am+1b*c2rn | m > 0}
(a) Design a Turing Machine that accepts the language L(M) [5 marks]
(b) Trace a computation of the Turing Machine that process a string aaabbcccc [4 marks]
(c) What is the shortest string in the language L(M) that accepted by the machine. [1 mark]
10
Question 10 [10 marks]
The table shows the 4 types of grammars in the Chomsky hierarchy. Fill up the blank fields
in the table below.
Table 1
Example** of Production rules
Type Grammar Languages Automaton Example of language L
(refer to the note below)
Recursively
Type-0
enumerable
Linear-bounded non-
Context-
Type-1
sensitive
deterministic Turing {a’V b ” | m 2 0}
machine
S -» aSb | X
Type-2 Context-free
A —> c A d |X
S —►aS | A.
Type-3 Regular Finite automata A-»aA|a {b’V | m, n £ 0}
B -> bB | b
END OF QUESTIONS
