MODEL PAPER

B. Tech (IT) Degree Examination

Third Year - First Semester

FORMAL LANGUAGES & AUTOMATA THEORY

Effective from the admitted batch of 2004-2005

Time: 3 hrs
Max Marks: 70

First Question is Compulsory

Answer any four from the remaining questions

All Questions carry equal marks

Answer all parts of any question at one place

1. a) Define Moore and Mealy machines with examples.
b) State Pumping lemma for regular sets
c) What is an ambiguous grammar? Give examples. How to eliminate ambiguity?
d) What is Post Correspondance Problem?
e) Define a Turing Machine with example.
f) Define the different types of grammar according to Chomsky Classification.
g) Define Push Down Automata with example

2. Find mininal DFA’s for the language L = {aⁿb^m, n>=2,m>=1}

3. Discuss the prove that the Closure properties of regular sets are closed.

4. a) State and Prove pumping lemma for CFL's

b) The language defined as L= {aⁿbⁿcⁿ/n>=1} is context free or not. Prove it.

5. a) S.T APDA that accepts by final state and PDA that accepts by empty store are quivalent.

b) Construct a PDA equivalent to the grammar S→ aAAA→ aS/b

6. a) Design a Turing machine that can compute proper subtraction i.e.. m _ n where m & n are positive integers
m _ n = m-n if m>n
=0 if m<=n

7. a) Find a Greibach normal form equivalent to the following CFG
S→AB/a, A→BS/b, B→SA/c

b) Remove all unit productions, all useless productions and all ε-productions for the grammar
S→aA/aBB,
A→aaA/ε,
B→bB/bbC, C→B.

8. Write notes on the following:
a) Myhill-Nreode Theorem
b) Chomsky Normal form
c) Recursively enumerable sets
d) DFA and NFA

Engineering Colleges in India
Get the most comprehensive list of Engineering Colleges in India

Engineering Admission Notifications
Recent Notifications for admissions to various Engineering Colleges in India