Exam Details
| Subject | Theory Of Computation | |
| Paper | ||
| Exam / Course | B.Tech In Computer Science And Engineering (BTCSVI) | |
| Department | School of Engineering & Technology (SOET) | |
| Organization | indira gandhi national open university | |
| Position | ||
| Exam Date | December, 2016 | |
| City, State | new delhi, |
Question Paper
No. of Printed Pages: 3 IBICS-OlSI
B.Tech. -VIEP -COMJ.>UTER SCIENCE AND ENGINEERING (BTCSVI) Term-End 00933 December, 2016
BICS-018 THEORY OF COMPUTATION
Time hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. Construct a DFA accepting all strings w over such that the number of in w is 3 mod 4. 5
Construct a finite automaton equivalent to the regular expression
1 5
2. What is a context-free grammar Construct a reduced grammar to the following grammar: 5
S aAa
A Sb/bCC/DaA
C abb/DD
E aC·
D aDA
What is pumping lemma for regular sets? Show that
L l n equal)1} is not regular. 5
3. Construct the transition systems equivalent to the regular expression
(ab (aa b). 5
Prove the following identity: 5
ab ab
4. Define ambiguous grammar and give an example. Show that the following grammar is ambiguous: 5
S aSbS bSaS E
Construct a finite automaton equivalent to the regular expression (10 0). 5
5. Describe Turing Machine. Design a Turing machine that accepts the language
L l w contains equal number of and 10
6. Define Deterministic Push Down Automata (DPDA). Design a DPDA for the language L l m n equal) 1}. 10
7. What is Church's hypothesis Explain it. Also describe undecidability and Rice's theorem. 10
8. Explain recursive and recursively enumerable languages with their applications and also compare and contrast decidability and undecidability. 10
9. What is the difference between recursive and recursively enumerable languages Show that the union of two recursively enumerable languages is recursively enumerable.
10. Write short notes on any two of the following: 2x5=10
NP-complete and NP-hard problems
Equivalence among DFA, NFA and NFA with e-move
Hamiltonian path and Chromatic number problems
B.Tech. -VIEP -COMJ.>UTER SCIENCE AND ENGINEERING (BTCSVI) Term-End 00933 December, 2016
BICS-018 THEORY OF COMPUTATION
Time hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. Construct a DFA accepting all strings w over such that the number of in w is 3 mod 4. 5
Construct a finite automaton equivalent to the regular expression
1 5
2. What is a context-free grammar Construct a reduced grammar to the following grammar: 5
S aAa
A Sb/bCC/DaA
C abb/DD
E aC·
D aDA
What is pumping lemma for regular sets? Show that
L l n equal)1} is not regular. 5
3. Construct the transition systems equivalent to the regular expression
(ab (aa b). 5
Prove the following identity: 5
ab ab
4. Define ambiguous grammar and give an example. Show that the following grammar is ambiguous: 5
S aSbS bSaS E
Construct a finite automaton equivalent to the regular expression (10 0). 5
5. Describe Turing Machine. Design a Turing machine that accepts the language
L l w contains equal number of and 10
6. Define Deterministic Push Down Automata (DPDA). Design a DPDA for the language L l m n equal) 1}. 10
7. What is Church's hypothesis Explain it. Also describe undecidability and Rice's theorem. 10
8. Explain recursive and recursively enumerable languages with their applications and also compare and contrast decidability and undecidability. 10
9. What is the difference between recursive and recursively enumerable languages Show that the union of two recursively enumerable languages is recursively enumerable.
10. Write short notes on any two of the following: 2x5=10
NP-complete and NP-hard problems
Equivalence among DFA, NFA and NFA with e-move
Hamiltonian path and Chromatic number problems
Other Question Papers
Departments
- Centre for Corporate Education, Training & Consultancy (CCETC)
- Centre for Corporate Education, Training & Consultancy (CCETC)
- National Centre for Disability Studies (NCDS)
- School of Agriculture (SOA)
- School of Computer and Information Sciences (SOCIS)
- School of Continuing Education (SOCE)
- School of Education (SOE)
- School of Engineering & Technology (SOET)
- School of Extension and Development Studies (SOEDS)
- School of Foreign Languages (SOFL)
- School of Gender Development Studies(SOGDS)
- School of Health Science (SOHS)
- School of Humanities (SOH)
- School of Interdisciplinary and Trans-Disciplinary Studies (SOITDS)
- School of Journalism and New Media Studies (SOJNMS)
- School of Law (SOL)
- School of Management Studies (SOMS)
- School of Performing Arts and Visual Arts (SOPVA)
- School of Performing Arts and Visual Arts(SOPVA)
- School of Sciences (SOS)
- School of Social Sciences (SOSS)
- School of Social Work (SOSW)
- School of Tourism & Hospitality Service Sectoral SOMS (SOTHSM)
- School of Tourism &Hospitality Service Sectoral SOMS (SOTHSSM)
- School of Translation Studies and Training (SOTST)
- School of Vocational Education and Training (SOVET)
- Staff Training & Research in Distance Education (STRIDE)
Subjects
- Advanced Computer Architecture
- Artificial Intelligence
- Computer Architecture
- Computer Networks
- Computer Organisations
- Cryptography And Network Security
- Data Structure
- Data Warehousing And Mining
- Database Management System
- Design and Analysis of Algorithm
- Digital Image Processing
- Discrete Maths Structure
- E-Business
- Formal Language And Automata
- Logic Design
- Microprocessor
- Mobile Computing
- Object Oriented Programming
- Operating Systems
- Parallel Algorithms
- Pattern Recognition
- Principles of Programming Lang.
- Real Time Systems
- Software Engineering
- Software Quality Engineering
- Software Reusability
- System Programming And Compiler Design
- Theory Of Computation
- Unix Internals And Shell Programming
- Web Technology