Andhra University 2005 B.Tech Information Technology - Formal Languages & Automata Theory - Question Paper
Thursday, 02 May 2013 05:50Web
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. |