Subjects
Advanced Java  2160707
Basic Electrical Engineering  3110005
Basic Mechanical Engineering  3110006
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Data Structure  2130702
Database Management Systems  2130703
Engineering Graphics & Design  3110013
English  3110002
Environmental Science  3110007
Information And Network Security  2170709
MathematicsI  3110014
Mobile Computing And Wireless Communication  2170710
Operating System  2140702
Physics Group  I  3110011
Physics Group  II  3110018
Programming for Problem Solving  3110003
Software Engineering  2160701
Theory Of Computation  2160704
Workshop  3110012
Semester
Semester  1
Semester  2
Semester  3
Semester  4
Semester  5
Semester  6
Semester  7
Semester  8
Theory Of Computation
(2160704)
TOC2160704
Winter2018
BE  Semester
Winter  2018

27/11/2018
Total Marks
70
Q1
(a)
Define one to one, onto and bijection function
3 Marks
(b)
Explain reflexivity, symmetry, and transitivity properties of relations
4 Marks
(c)
State the principle of mathematical induction and prove by mathematical induction that for all positive integers n 1+2+3+……..+n = n (n+1)/2
7 Marks
Q2
(a)
What are the closure properties of regular languages?
3 Marks
(b)
Explain moore machine and mealy machine.
4 Marks
(c)
What are the applications of finite automata? Draw Finite Automata to accept following.
7 Marks
OR
(c)
Define NFAΛ .Explain how to convert NFAΛ into NFA and FA with suitable example
7 Marks
Q3
(a)
State pumping lemma for regular languages.
3 Marks
(b)
Explain Union Rule and Concatenation Rule for Context Free Grammar
4 Marks
(c)
Write difference between DFA and NDFA. Convert the following NDFA to DFA.
7 Marks
OR
Q3
(a)
Define ContextSensitive Grammar. What is the language of following contextsensitive grammar?
3 Marks
(b)
Find a regular expression corresponding to each of the following subsets of {0, 1}*
4 Marks
(c)
What is CNF? Convert the following CFG into CNF.
7 Marks
Q4
(a)
What is Turing Machine? Write advantages of TM over FSM
3 Marks
(b)
Define CFG. When a CFG is called an ‘ambiguous CFG’?
4 Marks
(c)
Define PDA. Describe the pushdown automata for language {0
7 Marks
OR
Q4
(a)
Write a short note on Universal Turing Machine.
3 Marks
(b)
Describe recursive languages and recursively enumerable languages.
4 Marks
(c)
Explain push down automata with example and their application in detail
7 Marks
Q5
(a)
Define grammar and chomsky hierarchy
3 Marks
(b)
What are the applications of regular expressions and finite automata?
4 Marks
(c)
Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}.
7 Marks
OR
Q5
(a)
Compare FA, NFA and NFA^
3 Marks
(b)
Write a short note on churchturing thesis
4 Marks
(c)
Explain primitive recursive function by suitable example
7 Marks