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
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
Q1
(b)
Explain reflexivity, symmetry, and transitivity properties of relations
4 Marks
Q1
(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
Q2
(b)
Explain moore machine and mealy machine.
4 Marks
Q2
(c)
What are the applications of finite automata? Draw Finite Automata to accept following.
7 Marks
Q2
OR
Q2
(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
Q3
(b)
Explain Union Rule and Concatenation Rule for Context Free Grammar
4 Marks
Q3
(c)
Write difference between DFA and NDFA. Convert the following NDFA to DFA.
7 Marks
Q3
OR
Q3
(a)
Define ContextSensitive Grammar. What is the language of following contextsensitive grammar?
3 Marks
Q3
(b)
Find a regular expression corresponding to each of the following subsets of {0, 1}*
4 Marks
Q3
(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
Q4
(b)
Define CFG. When a CFG is called an ‘ambiguous CFG’?
4 Marks
Q4
(c)
Define PDA. Describe the pushdown automata for language {0
7 Marks
Q4
OR
Q4
(a)
Write a short note on Universal Turing Machine.
3 Marks
Q4
(b)
Describe recursive languages and recursively enumerable languages.
4 Marks
Q4
(c)
Explain push down automata with example and their application in detail
7 Marks
Q5
(a)
Define grammar and chomsky hierarchy
3 Marks
Q5
(b)
What are the applications of regular expressions and finite automata?
4 Marks
Q5
(c)
Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}.
7 Marks
Q5
OR
Q5
(a)
Compare FA, NFA and NFA^
3 Marks
Q5
(b)
Write a short note on churchturing thesis
4 Marks
Q5
(c)
Explain primitive recursive function by suitable example
7 Marks