B.C.A. (Semester (CBCS) Examination Nov/Dec-2018
THEORY OF COMPUTATION
Time: 2½ Hours Max. Marks: 70
Instructions: All questions are compulsory.
Figures to the right place indicate full marks.
Q.1 Choose correct alternatives: 14
Pumping lemma is generally used to prove that:
Language is infinite
Language is not regular
Whether two given regular expressions of a regular language are
equivalent or not
None of these
"CFG" stands for
Context Free Graph Context Free Grammar
Context Finite Graph Context Finite Grammer
Language generated by type 3 grammar is
Unrestricted language Context free language
Regular language Context sensitive language
is an abstract or user defined entity.
Symbol Alphabet
String Language
In case of, if we provide some input to some state then we can
get only one state as next state.
DFA NFA
Both a and b None of these
Regular expression which generated the language ε, aa, ba, ab, bb …

ab*
Transition graph is said to be FA if it
final state initial state
non final state both initial and final state
Reflexive and Transitive closure of R denoted

None of these
In the internal state of the machine alters, when the machine
receives an input and generates the required output.
FA NFA
FSM Basic machine
10) Transition function of mealy machine is

Σ
Page 2 of 3
SLR-SH-27
11) A grammar is said of be linear if it contains at more than one variable at the
right side of production.
True False
12) Grammar represented by tuples.
5 4
6 7
13) If then r

a a5
14) One or more number of followed by one or more number of is denoted
by


Q.2 Answer any Four of the following:- 08
Define non deterministic Finite automata.
Define grammar.
Define derivation tree. List the types of derivation.
Construct DFA to accept a string ending with pqq over Σ
Let R be a relation in Find
Answer any two of the following questions:- 06
Define Mealy machine to find out complement of a given binary
number.
Give the regular expression for the language:
Set of all string beginning with a and ending with b over Σ
ii) Set of all strings that contains zero or more number of over
Σ 0
iii) Set of all string containing three consecutive zeros over Σ 0,1
Find the CFL for the following grammars.


ii) Aa/Bb
aA/a

Q.3 Answer any two of the following:- 08
Define FSM. Design FSM for divisibility for 3 tester.
Find the context free grammar

ii)
Let Write the
following sets by listing their elements.

ii)
iii)
iv)
Answer any one of the following:- 06
Convert NFA to its equivalent DFA is shown in
table.
Q/Σ 0 1
p Pq p
q r r
r s
s s s
Page 3 of 3
SLR-SH-27
What are the languages for the following regular expression?

ii)
iii)
iv)

vi)
Q.4 Answer any two of the following:- 10
Find the leftmost derivation, rightmost derivation, also construct
derivation tree for the string "0100" by using following grammar.
S → 0AS 0
A → SS 10 0S S1A
Construct FA for following RE for
Construct CNF for following grammar
S S S S S id
Answer any one of the following:- 04
Explain the Chomsky hierarchy.
Explain concept of finite Automata with output in detail.
Q.5 Answer any two of the following:- 14
Find GNF for the following grammar.
A*A |a.
What is DFA minimization? Minimize the following DFA.
Q/Σ 0 1
B F
B G C
A C
D C G
E H F
F C G
G G E
H G C
Define the following terms.
DFA
ii) NFA with
iii) Symbol
iv) Regular expression
Unit production
vi) Variable
vii) 𝜀-production