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


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