Subjects
Applied Mathematics for Electrical Engineering  3130908
Complex Variables and Partial Differential Equations  3130005
Engineering Graphics and Design  3110013
Basic Electronics  3110016
MathematicsII  3110015
Basic Civil Engineering  3110004
Physics Group  II  3110018
Basic Electrical Engineering  3110005
Basic Mechanical Engineering  3110006
Programming for Problem Solving  3110003
Physics Group  I  3110011
MathematicsI  3110014
English  3110002
Environmental Science  3110007
Software Engineering  2160701
Data Structure  2130702
Database Management Systems  2130703
Operating System  2140702
Advanced Java  2160707
Compiler Design  2170701
Data Mining And Business Intelligence  2170715
Information And Network Security  2170709
Mobile Computing And Wireless Communication  2170710
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
7
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