Roll No…………………..
Dr B R Ambedkar National Institute of Technology, Jalandhar
B.Tech 5th Semester (Computer Science & Engineering)
CSPC–303, Theory of Computation
End-Semester Examination, December-2024
Duration: 03 Hours Max. Marks: 50 Date: 02 December 2024
Marks Distribution & Mapping of Questions with Course Outcomes (COs)
Question Number 1 2 3 4 5 6
Max. Marks 6 4 8 4,4 4,5 15
CO No. 1 1,2 3 3,4 4 3,4
Cognitive Level U Ap E C,Ap An,E E, C
Section/Chapter/Unit 1 2 3,4 5,6 6,7 7,8
Remember (R), Understand (U), Apply (Ap), Analyse (An), Evaluate (E), and Create (C)
Note: Attempt all the questions. Write all the possible steps whenever required.
1. a) Construct a Deterministic Finite Automaton (DFA) for the
language 𝐿1 where 𝐿1 = {𝜙 ∈ (𝑎, 𝑏, 𝑐 )∗ | 𝜙 starts and ends
with the same symbol}.
b) Design a DFA for the language containing a set of strings of
0’s and 1’s except those containing substring 110 over input
symbol {0, 1}.
c) Design a NFA to accept the set of all strings starting with ‘a’
followed by ‘a’ or ‘b’ and ending with ‘a’ or any number of b’s.
2. Design a ∈-NFA to accept decimal numbers. A valid decimal
number may have the following characteristics:
The sign (either '+' or '-') is optional.
A string of digits (which can be empty) must precede the
decimal point.
The decimal point is mandatory.
A string of digits (which can also be empty) may follow the
decimal point.
1
3. a) Justify which language over {0,1} does the CFG with
productions S → 00S | 11S | S00 | S11 | 01S01 | 01S10 | 10S10 |
10S01 | ∈ generate?
b) Explain how ∈-productions are eliminated from a grammar
whose language doesn’t have empty string? Remove ∈-
productions from the grammar given below.
S → a | aA | B | C
A → aB | ∈
B → Aa
C → aCD
D → ddd
c) Convert the following grammar to Chomsky Normal form.
S → A | AB0 | A1A
A → A0 | ∈
B → B1 | BC
C → CB | CA | 1B
d) Prove with the help of pumping lemma that language 𝐿1 =
{𝑎𝑛 𝑏𝑛 𝑐 𝑛 | 𝑛 > 0} is not context free language.
4. a) Obtain the minimized DFA equivalent to the given finite
automaton.
2
b) (i) Derive a regular expression that represents the language
accepted by the state diagram shown in the below figure.
(ii) Explain Chomsky's Classification of Grammars, detailing
each type of grammar along with the specific conditions
associated with their production rules.
5. a) Construct the context free grammar generating following
i) 𝐿2 = {𝑤 | 𝑛𝑎 (𝑤) > 𝑛𝑏 (𝑤)}
ii) 𝐿3 = {𝑤 ∶ |𝑤|𝑚𝑜𝑑 3 = 0}
iii) 𝐿4 = {𝑎𝑚 𝑏𝑛 | m ≠ n, m ≥ 0, n ≥ 0}
iv) 𝐿5 = {𝑎𝑛 𝑏𝑚 𝑐 𝑚 𝑑 𝑛 | 𝑛 ≥ 1, 𝑚 ≥ 1}
b) Reduce the following grammars to GNF:
S→AB, A→BSB, A→BB, B→aAb, B→a, A→ b
6. (a) Construct the PDA for the language 𝐿6 =
{𝑎𝑛 𝑏𝑚 𝑐 𝑚 𝑑 𝑛 | 𝑛, 𝑚 ≥ 1}
(b) Construct a context free grammar (G) which accepts N(A),
where 𝐴 = ({𝑞0 , 𝑞1 }, {𝑎, 𝑏}, {𝑧0 , 𝑧}, 𝜕, 𝑞0 , 𝑧0 , ɸ) and the
transition function 𝜕 is given by
𝜕(𝑞0 , 𝑏, 𝑧0 ) = {(𝑞0 , 𝑧𝑧0 )} 𝜕(𝑞0 , 𝑎, 𝑧) = {(𝑞1 , 𝑧)}
( )
𝜕 𝑞0 , ˄, 𝑧0 = {(𝑞0 , ˄)} 𝜕 (𝑞1 , 𝑏, 𝑧) = {(𝑞1 , ˄)}
𝜕(𝑞0 , 𝑏, 𝑧) = {(𝑞0 , 𝑧𝑧)} 𝜕(𝑞1 , 𝑎, 𝑧0 ) = {(𝑞0 , 𝑧0 )}
(c) Design a Turing Machine that accepts the set of all
palindromes over the binary alphabet {0,1}. A palindrome is a
binary string that reads the same forward and backward.
*****
