FORMAL LANGUAGES and AUTOMATA THEORY - FLAT Paper 1

Download FREE Computer Science Engineering (CSE Engg. Branch) Previous 5 Years solved Regular and Reappear Question Papers B.tech PTU (2007, 2006, 2005, 2004, 2003) and related Placement Technical Interview Questions for subject FORMAL LANGUAGES and AUTOMATA THEORY - FLAT

(Semester 7th) .FORMAL LANGUAGES and AUTOMATA THEORY (CS - 404)
Time: 03 Hours
Maximum Marks: 60
Instruction to .Candidates:
1)Section - A is compulsory.
2)Attempt any Four questions from Section - B.
3)Attempt any Two questions from Section - C.
. Section - A .
Ql)
a) Define the term Automata and name the various types of languages
accepted by an Automata. .
b) Find the language generated by Grammer.
S ~ OSl/OAl, A ~ lA/I
c) What do you mean by ambiguity of a Grammer?
d) Test whethel 001100,001010 are in the language generated by Grammer
S ~ OS 1/0AJO/1B/l.
A ~ OAJO, B ~ lB/l
e) Define the terms canonical Derivation and context sensitivity in the context
of Derivation languages.
f) What is a regular Grammer.
g) Differentiate between leftmost and rightmost derivation trees.
h) Name the various operations that can ~e performed on languages.
i) Describe the retation between linear bounded Automata and context sensitive Grammer.
j) What is cellular Automata.

Section - B

Q2) Construct a mealy machine which can output EVEN, ODD accordin as the total number of 2's encountesed is even or odd. The input symbols are 0 and 1.
Q3) Explain in brief the propertios ofLR (K) Grammers.
Q4) Show that the Grammer S ~ aB/ab, A ~ aAB/a, B ~ ABb/b is
Ambiguous.
Q5) Let L = {ambn/n<m} Construct a context free Grammer accepting L.
Q6) Describe the terms Univelsatility and complexity variants in the conte'xt of
cellular Automa.

Section - C

Q7) Design a. tusing maohine M to recognise the language {l n2n3 n/n> I}. Also
derive the computation sequence for the input 112233.
Q8) Reduce the following Grammer to Grelba~h normal form.
S~AB,A~BSB,A ~BB,B ~aAb,B ~a,A~b
Q9) Write short notes on the following.
(a) Closure properties of languages.
(b) SyntxAnalysis.
(c) Kusoda Normal form.
(d) PUsh Down Automata.