Exam Details
| Subject | theory of computation (new) | |
| Paper | ||
| Exam / Course | f.y. m.tech. (civil -structural engg.) | |
| Department | ||
| Organization | solapur university | |
| Position | ||
| Exam Date | 06, December, 2018 | |
| City, State | maharashtra, solapur |
Question Paper
F.Y. M.Tech. (Semester (CBCS) Examination, 2018
Theory of computation
Day and Date Thursday, 6-12-2018 Total Marks 70
Time 10.00 a.m. to 1.00 p.m.
Section I
1. Answer any four 24
Define FA. Construct the FA for the string 110
I llustrate ENFA and EDFA in decidability and prove that they are decidable
languages.
What is context Free Grammar Give the automata accepting CFL with its
properties.
What is Halting Problem Prove that ATM is Undercidable.
Prove that a language is turing recognizable iff some enumerator enumerates it.
2. Answer the following 6
Give a formal definition of a TM. Design a TM for a language L {02n
3. Answer the following 5
What is diagonalization method Prove the corollary languages are not
turing recognizable''.
4. Answer any four 24
Prove that ETM is undecidable. Elaborate reducibility.
What are tractable and intractable problems Elaborate.
Define computation history and linear bounded automation Prove that
ALBA is undecidable.
Elaborate recursion theorem with its applications.
Elaborate PCP problem with its theorem proof.
5. Answer the following 6
If M2 are TMs then prove that EQTM is
undecidable.
6. Answer the following 5
Elaborate growth rate of functions.
Theory of computation
Day and Date Thursday, 6-12-2018 Total Marks 70
Time 10.00 a.m. to 1.00 p.m.
Section I
1. Answer any four 24
Define FA. Construct the FA for the string 110
I llustrate ENFA and EDFA in decidability and prove that they are decidable
languages.
What is context Free Grammar Give the automata accepting CFL with its
properties.
What is Halting Problem Prove that ATM is Undercidable.
Prove that a language is turing recognizable iff some enumerator enumerates it.
2. Answer the following 6
Give a formal definition of a TM. Design a TM for a language L {02n
3. Answer the following 5
What is diagonalization method Prove the corollary languages are not
turing recognizable''.
4. Answer any four 24
Prove that ETM is undecidable. Elaborate reducibility.
What are tractable and intractable problems Elaborate.
Define computation history and linear bounded automation Prove that
ALBA is undecidable.
Elaborate recursion theorem with its applications.
Elaborate PCP problem with its theorem proof.
5. Answer the following 6
If M2 are TMs then prove that EQTM is
undecidable.
6. Answer the following 5
Elaborate growth rate of functions.
Other Question Papers
Subjects
- advanced design of concrete structures
- advanced design of foundation
- advanced digital signal processing
- advanced network system
- advanced solid mechanics (new)
- advanced structural analysis
- advanced vibrations and acoustics
- antena design and applications
- applied algorithms
- computational techniques in design enginering
- computer aided design (elective – i)
- data mining
- digital design and verification
- elective – 1 : advanced embedded system
- elective – i : analog and digital cmos vlsi design
- elective – i : biomedical signal processing
- elective – i : computer vision
- elective – i : image and video procesing
- elective – i : mechanical system design
- elective – i : natural language procesing
- elective – i : neural networks and fuzzy control systems
- elective – i : soft computing
- elective – i : wireles sensor networks
- industrial instrumentation
- machine learning
- object oriented software enginering (elective – i)
- reliability enginering (elective – i)
- research methodology and ipr
- soft computing methods
- structural dynamics
- theory of computation (new)
- voice and data networks