FORMAL LANGUAGES AND AUTOMATA THEORY Prefinal Question papers for III IT
10/26/10Posted by
Fulto
0 Comments
Set No. 1
FORMAL LANGUAGES AND AUTOMATA THEORY
B.Tech III -I Semester (Information Technology)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1 A).Construct DFA and NFA accepting the set of all strings not accepting 101 as substring.
B).Define NFA with example and Draw the transition diagram of a FA which accepts all strings of 1’s and 0’s in which both the number of 0’s and 1’s are even? [8 + 8]
2. A) Discuss about FA with outputs in details?
B) Write the steps in construction of minimization of automata? [8 + 8]
3. A) Show that L ={ WW|W Є {a,b}* } is not regular.
B) Write Pumping lemma Applications? [8 + 8]
4. A) Eliminate – productions from the grammar G given as
A →aBb|bBa
B →aB|bB|
B) Convert the following grammar to GNF [8 + 8]
5.A) Define PDA and Explain the acceptance of final and empty states?
B) Design PDA generating L= {WcWR| W Є {a, b}*} [8 + 8]
6.Explain the procedure to convert CFG to PDA with suitable example?[16]
7. Design Turing Machine for L = {0n 1n 0n |n>0} [16]
8.Construct LR(0) items for the given grammar [16]
S’ →S
S →AS |a
A →Bb |b
*********** ALL THE BEST ***********
Set No. 2
FORMAL LANGUAGES AND AUTOMATA THEORY
B.Tech III -I Semester (Information Technology)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1.a) Design a DFA, M that accepts the language L(M)={w/w Є {a,b}*} and w does not contain 3 consecutive b’s.
b) Define NFA with epsilon and explain with an example? [8 + 8]
2.Expalin the mealy and moore machine s with suitable example?and its conversion?[16]
3.Construct an NFA for the following
a) R=01[((10)*+111)*+0]*1 b) ((01 + 10)*00)* [8 + 8]
4.a) Find the LMD and RMD for the word abba in the grammar
S →AA , A →aB , B→ bB/
b)Prove that the following language is not CFL L={an bnc j/n<j<2n}
5.a) Explain Chomsky hierarchy?
b) Simplify the following grammar
S →AB, A→ a, B→ c ,B→ b, C→ D , D→ E [8 + 8]
6. a)Define DPDA .Explain with an example?
b) B) Design PDA generating L= {WCWT| W Є {a, b}*}
7.a) Define a Turing Machine mathematically. Define the term ‘move’ in a TM
b)Briefly explain the properties of REL.
8. Discuss: a) The Hierarchy theorem b) LR(0) grammar c Universal Turing Machine [6 + 5 + 5]
*********** ALL THE BEST ***********
Set No. 3
FORMAL LANGUAGES AND AUTOMATA THEORY
B.Tech III -I Semester (Information Technology)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1.a) Design to accept strings with c and d such that number d’s are divisible by 4.
b) Design DFA which accepts language L = {0,000,00000,……} over {0} [8 + 8]
2. a) Write the steps in minimization of FA?
b) Defferentiate NFA ,NFA with epsilon and DFA? [8 + 8]
3 Write definition of RE and Construct DFA for the following RE (ab U aba)*a [16]
4 a) List the properties of CFLS
b) Show that L =[a i b j / j= i2} is not CFL? [8 + 8]
5.a) When is a grammar is said to be in reduced form
b) Convert the following grammar to GNF
A1 →A2A3
A2 →A3A1/b
A3 →A1A2/a [4+12]
6 a)Define PDA.In what ways a PDA can show the acceptance of a string .
b) Construct a PDA generating L= {WWR| W Є {a, b}*} such that L= L(M). [8 + 8]
7.a)Explain various types of Turing Machines?
b) Design a Turing Machine to add two given integers. [8 + 8]
8.a) Write short notes on LBA
b) Write short notes on : Church’s hypothesis , Ardens Lemma and NPDA. [4+ 12]
*********** ALL THE BEST ***********
Set No. 4
FORMAL LANGUAGES AND AUTOMATA THEORY
B.Tech III -I Semester (Information Technology)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
1.a) Write the applications of finite automata?
b) Define the following terms mathematically i)NFA ii)DFA iii) Moore iv) Mealy [8 + 8]
2. a) Write the steps for Equivalence of two FA?
b) Differentiate Moore and Mealy machine? [8 + 8]
3a) Obtain transition diagram and a regular expression to accept string of 0’s and 1’s having no two consecutive 0’s?
b) Obtain transition diagram and a regular expression to accept string of a’s and b’s whos e 10 th symbol from right end is b.
4 a) List the properties of RE?
b) Show that L =[a n b n / n>1} is not a RL? [8 + 8]
5.a) When is a grammar is said to be in reduced form
b) Convert the following grammar to GNF
S AB
A →BS/b
A3 →SA|a [4+12]
6 a)Define PDA.Let G be the grammar given by
S →Aabb/Aaa
A →Abb/A
B→ bBB/A Construct the PDA that accepts the language generated by this G
b) Construct a PDA generating L= {WWR| W Є {a, b}*} such that L= L(M). [8 + 8]
7.a)Explain various types of Turing Machines?
b) Design a Turing Machine to add two given integers. [8 + 8]
8.a) Write short notes on
a)P and NP Problems b)CSL and C)Decidability of PCP [5+5+6]
*********** ALL THE BEST ***********
People who read this post also read :
Labels:
DDB
Subscribe to:
Post Comments (Atom)