Andhra University 2005 B.Tech Information Technology - Formal Languages & Automata Theory - Question Paper

MODEL PAPER

B. Tech (IT) Degree exam

Third Year - 1st Semester

FORMAL LANGUAGES & AUTOMATA THEORY

Time: three hrs
Max Marks: 70

First ques. is Compulsory

ans any 4 from the remaining ques.

All ques. carry equal marks

ans all parts of any ques. at 1 place

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

2. obtain mininal DFA’s for the language L = {anbm, n>=2,m>=1}

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

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

b) The language described as L= {anbncn/n>=1} is situation 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 calculate 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) obtain a Greibach normal form equivalent to the subsequent CFG
S?AB/a, A?BS/b, B?SA/c

b) Remove all unit productions, all useless productions and all e-productions for the grammar
S?aA/aBB,
A?aaA/e,
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

Earning:   Approval pending.