Roll No.

Pandit Deendayal Energy University

End Semester Examination – (May, 2024)
B. Tech. (ComputerScience andEngineering)
Semester - III
Date: 08/05/2024
Course Name: Theory of Computation Time: 3 hours
Course Code: 20CP206T Max. Marks: 100

Instructions:
1. Do not write anything other than your roll number on question paper.
2. Assumesuitable data wherever essential andmention it clearly
3. Writing appropriate units. nomenclature7anddrawing neat sketches/schematicswhereverrequired is an integral part
of the answer.

Course
Question Marks Outcomes
Description
No. :COIS
1. 7
a) Cla,ity th, „„„,pt9 „F,mili„ .f L,.g.,g„” i„ „f„,.„ t, Theory of
Computation with suitable diagram. Provide examples of machines
associated with each language famil

b) Write 6
a context free grammar for a language of even length strings.
Construct a nondeterministic pushdown automaton for a language 7 C04
C)
L=a''b2'1+ljn>= 1.
OR
Construct a nondeterministic pushdown automaton for a language
L=Oili2kl i––j or j==k; i, j, k>=1.
2. a) 1 10
L = {ww I w C (0,1)*}
OR
C06
Desjgn a Linear Bounded Automaton(LB A) for the language
L = {aibick t i+j = k; i, j, k ? 1}
a b’s. 10

7
3. a) Design a Context Sensitive Grammar for anb'''c"cf" t m3 n = 1

OR
Design a Context Free Grammar for an expression over {[9 ]} such that
(i) every len parenthesis has a matching right parenthesis,
(ii) the matched pairs are well nested.
o it)ach 10
Normal Form (GNF): C05

s –> XB 1 AA
A –, a ISA
B--–> b
}L -–> a
t WG) 3
to Push Down Automata (PDA

Page 1 of 2
4. a) Construct a minimal DFA accepting a set of strings over {a, b} in which 7
{a2bwa2 1w e{a, b}#}
Here 'w’ is the substring containing alphabets over any number of 'a’ and
'b’ ranging from zero to infinity
b) Let L be the language which is represented by: 7
L = {w e {a, b}81w contains an equal number of occurrences of ab and CO 1
ba}
For example,ababa e L (two occurrences of ab, andtwo of ba), whereas
bbaba e L (one occurrence of ab, and two of ba).
Provide a regular expression whose language is L.

5. a) Considerthe following context-free grammar to generate arithmetic 6

expressionsin one variable a, involving addition and multiplication
operations only. The Grammar: S –> a 1S + S 1S x S
Here, S is the start symbol.
Drawall the possible parse trees for the string a + a x a + a following the
glverl grarnrrlar.
b) Whatare the different techniquesto reduce a CFG?Use 'Elimination of 6 C03
Unit Production’ruleto simplify the CFG consists of following production
rule
S–bOA jIB C
A –> os Eoo
B –> IIA
(A-–> 01
6. a) Minimize the following DFA of Figure 1: 8
0,1
n\

C02

Figure 1

I Moore 6
machines.
Explain how the choice between these models can impact the design and
implementation of sequential circuits.

Page 2 of 2