Exam Details
| Subject | Formal Language And Automata | |
| 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-OIO I
B.TeCh. -VIEP -COMPUTER SCIENCE AND
ENGINEERING (BTCSVI)
Term-End Examination
December, 2016
BICS-010 FORMAL LANGUAGES AND AUTOMATA
Time hours Maximum Marks: 70
Note: Attempt any Seven, questions. All questions carry equal marks.
1. Explain the terms regular sets, regular expressions and closure properties. 5
Let R be a relation on the set 3. Find R*. 5
2. Construct a finite automaton to accept the regular expression
(00 11) 5
Construct FA equivalence to the following regular expression: 5
r 1
3. Construct a DFA for the regular expression r abb and optimize the states. 5
Construct NFA for the following regular expression: 5
10* 01*0
4. What is Chomsky normal form? Convert the following context-free grammar to Chomsky normal form:
S AaB 1 aaB 5
B bbA IE
Convert the following grammar into CNF : 5
S aAD
1 bAB
B b
D d
5. Define push down automata and explain its model with the help of a neat diagram. 5
Prove that if L is for some PDA M2, then L is for some PDA M1. 5
6. State and explain CYK algorithm using some examples. 5
List the problems that are decidable for deterministic CFLs. 5
7. Explain the terms turing machine and Recursively enumerable language. 5
7. Explain the procedure involved in the design of a turing machine. 5
8. Write a short note on universal turing machine. 5
Explain in detail: Church's thesis; 5
9. Explain Chomsky hierarchy of languages with the help of a neat diagram. 10
10. Show that L is a context sensitive language. 5
Discuss briefly about undecidability of the Post correspondence problem. 5
B.TeCh. -VIEP -COMPUTER SCIENCE AND
ENGINEERING (BTCSVI)
Term-End Examination
December, 2016
BICS-010 FORMAL LANGUAGES AND AUTOMATA
Time hours Maximum Marks: 70
Note: Attempt any Seven, questions. All questions carry equal marks.
1. Explain the terms regular sets, regular expressions and closure properties. 5
Let R be a relation on the set 3. Find R*. 5
2. Construct a finite automaton to accept the regular expression
(00 11) 5
Construct FA equivalence to the following regular expression: 5
r 1
3. Construct a DFA for the regular expression r abb and optimize the states. 5
Construct NFA for the following regular expression: 5
10* 01*0
4. What is Chomsky normal form? Convert the following context-free grammar to Chomsky normal form:
S AaB 1 aaB 5
B bbA IE
Convert the following grammar into CNF : 5
S aAD
1 bAB
B b
D d
5. Define push down automata and explain its model with the help of a neat diagram. 5
Prove that if L is for some PDA M2, then L is for some PDA M1. 5
6. State and explain CYK algorithm using some examples. 5
List the problems that are decidable for deterministic CFLs. 5
7. Explain the terms turing machine and Recursively enumerable language. 5
7. Explain the procedure involved in the design of a turing machine. 5
8. Write a short note on universal turing machine. 5
Explain in detail: Church's thesis; 5
9. Explain Chomsky hierarchy of languages with the help of a neat diagram. 10
10. Show that L is a context sensitive language. 5
Discuss briefly about undecidability of the Post correspondence problem. 5
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