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 | June, 2016 | |
| City, State | new delhi, |
Question Paper
No. of Printed Pages: 3 IBICS-OI0 I
B.Tech. -VIEP -COMPUTER SCIENCE AND ENGINEERING (BTCSVI)
Term-End.Examination
00496 June, 2016
BICS-010 FORMAL LANGUAGES AND AUTOMATA
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. What are the concepts of Automata Theory Explain with the help of some examples. 5
Define formal definition of finite automata. State the diagrams of the two-state finite automaton and five-state finite automaton. 5
2. Define regular expressions and find the regular expression for the following: 5
L |every odd position of w is a 1 defined over
Prove disprove the following for the regular expressions r and s 5
(rs r
3. Show that L {ww w E is not regular. 5
Prove L w E is not regular using pumping lemma. 5
4. Define ambiguous grammar and give an example to show that the following grammar is ambiguous. 5
S aSbS bSaS
When is a grammar said to be in reduced form? Explain. 5
5. Convert the following context-free grammar to pushdown automata: 5
S aA bB
A aB a
B b
State and explain Myhill-Nerode theorem with the help of example grammar. 5
6. Show the equivalence of CFL and PDA. 10
7. Design a Turing Machine that recognizes the set 1^n n 5
Design a Turing Machine which will recognize the strings containing equal number of and 1's. 5
8. What is recursively enumerable language Explain with the help of an example. 5
Show that if L and L^R are recursively enumerable, then L is recursive. 5
9. What are NP Complete and NP Hard problems Explain with the help of examples. 5
Find whether the post correspondence problem P has a match. Give the solution. 5
10. What is halting problem? Explain. 5
Explain Turing reducibility machine. 5
B.Tech. -VIEP -COMPUTER SCIENCE AND ENGINEERING (BTCSVI)
Term-End.Examination
00496 June, 2016
BICS-010 FORMAL LANGUAGES AND AUTOMATA
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. What are the concepts of Automata Theory Explain with the help of some examples. 5
Define formal definition of finite automata. State the diagrams of the two-state finite automaton and five-state finite automaton. 5
2. Define regular expressions and find the regular expression for the following: 5
L |every odd position of w is a 1 defined over
Prove disprove the following for the regular expressions r and s 5
(rs r
3. Show that L {ww w E is not regular. 5
Prove L w E is not regular using pumping lemma. 5
4. Define ambiguous grammar and give an example to show that the following grammar is ambiguous. 5
S aSbS bSaS
When is a grammar said to be in reduced form? Explain. 5
5. Convert the following context-free grammar to pushdown automata: 5
S aA bB
A aB a
B b
State and explain Myhill-Nerode theorem with the help of example grammar. 5
6. Show the equivalence of CFL and PDA. 10
7. Design a Turing Machine that recognizes the set 1^n n 5
Design a Turing Machine which will recognize the strings containing equal number of and 1's. 5
8. What is recursively enumerable language Explain with the help of an example. 5
Show that if L and L^R are recursively enumerable, then L is recursive. 5
9. What are NP Complete and NP Hard problems Explain with the help of examples. 5
Find whether the post correspondence problem P has a match. Give the solution. 5
10. What is halting problem? Explain. 5
Explain Turing reducibility machine. 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