Get premium membership and access revision papers, questions with answers as well as video lessons.
Comp 303: Theory Of Computation Question Paper
Comp 303: Theory Of Computation
Course:Bachelor Of Science In Computer Science
Institution: Chuka University question papers
Exam Year:2011
CHUKA UNIVERSITY
KAPKWEN@CU2014
UNIVERSITY EXAMINATIONS
YEAR THREE EXAMINATION FOR THE AWARD OF THE DEGREE OF BACHELOR OF SCIENCE (COMPUTER SCIENCE)
COMP 303: THEORY OF COMPUTATION
STREAM: B.SC (COMP. SCIENCE) Y3S1 TIME: 2 HOURS
DAY/DATE: TUESDAY 2/8/2011 11.30 A.M. – 1.30 P.M
INSTRUCTIONS:
1. Answer question ONE and any other two questions
2. Marks are awarded for clear and concise answers
Question ONE (30 Marks)
(a) Briefly describe the following terms as used in theory of computation. [10 marks]
(i) P Problem
(ii) Non-deterministic Finite automata
(iii) Turing machine
(iv) Push Down Automata
(v) Deterministic Finite automata
(b) Represent the following deterministic Finite Automata using a transition
Table. [5 marks]
(c) Given the Production rules;
S->AB|AaCbB
A->Aa|?
B->bB| ?
C->baC|ba
Give a derivation tree for aababbb [5 marks]
(d) Use Chomsky hierarchy to show a containment hierarchy of classes of formal languages. [5 marks]
(e) Models are an important ways of studying physical and social phenomena, such as Weather systems, spread of epidemics, Chemical molecules. What is a model? List FOUR characteristics of a model? [5 marks]
Question TWO-(20 marks)
(a) What do you understand from the following terms as used in theory of
computation? [6 marks]
(i) Regular expression
(ii) Context free grammar
(iii) Ambiguous grammar
(b) Parsing determines whether w e L (G) .Parsing constructs implicitly or explicitly a derivation tree (Parse tree) for w .Discuss FIVE applications of parse tree.
[10 marks]
(c) What is an NP Complete problem? Give an example of an NP Problem?[4 arks]
Question THREE -20 Marks
Let M1 be the DFA given by:
M1= (Q1, ?, s1, q0, F1)
Q1= {q0, q1, q2,q3}
?= {a, b}
F1= {q3}
The transition function s1:Q1 ? ?? Q1 is
Q1 s1 (q, a) s1 (q,b)
q0 q1 q2
q1 q0 q3
q2 q3 q0
q3 q2 q1
(a) Describe what these represent in the machine [5 marks]
Q1, ?, s1,q0, F1
(b) Draw a state diagram to show how the machine responds to the following input
(i) abbab [5 marks]
(ii) baabba [6 marks]
(c) Give TWO everyday applications of a machine such as this. [2 marks]
(d) What is a dead/error state? Show it diagrammatically? [2 marks]
Question FOUR - 20 marks
Below is an NFA Machine
s1 (q, ?) s1(q, a ) s1(q, b )
q0 ? {qo,q1} {q3}
q1 ? ? {q2}
q2 q0 ? {q2}
q3 ? {q4} {?}
q4 ? ? {q3,q4 }
(a) Draw the state diagram for M1. [8 Marks]
(b) What is L (M1)? [7 marks]
(c) Give TWO characteristics of an NFA in normal form. [2 marks]
(d) Using a diagram, give an example of a machine in normal form. [3 marks]
Question FIVE - 20 marks
(a) A good model for the “computing agent” entity must capture the fundamental properties of a computing agent. A Turing machine has the required features for a computing agent.
Using a diagram if necessary, explain the FIVE operations of Turing machine.
[5 marks]
(b) An Odd parity bit scheme has the following characteristics;
-An extra bit attached to the end of a string of bits
-Set up so that the number of 1s in the whole string, including the parity bit, is odd
-If the string has an odd number of 1s, parity bit is set to 0
-If the string has an even number of 1s, parity bit is set to 1
Draw a state diagram to represent this Parity Bit Machine using the following Turing
Machine program. [8 marks]
(1, 1, 1, 2, R)
(1, 0, 0, 1, R)
(2, 1, 1, 1, R)
(2, 0, 0, 2, R)
(1, b, 1, 3, R)
(2, b, 0, 3, R)
(c) (i) Write a Turing Machine program for the following State diagram.
[2 marks]
(ii) Give an alternative solution to the one given in c(i) above. [2 marks]
(d) Give THREE practical of unsolvable problems related to the halting problem.
[3 marks]
------------------------------------------------------------------------------------------------------------
KAPKWEN@CU2014
More Question Papers
Popular Exams
Return to Question Papers