Subjects
Advanced Java  2160707
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Data Structure  2130702
Database Management Systems  2130703
Information And Network Security  2170709
MathematicsI  3110014
Mobile Computing And Wireless Communication  2170710
Operating System  2140702
Software Engineering  2160701
Theory Of Computation  2160704
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