10CS56 Formal Languages And Automata Theory B.E Question Bank : sjbit.edu.in

Name of the College : SJB Institute of Technology
Subject Code/Name : 10CS56- FORMAL LANGUAGES AND AUTOMATA THEORY
Dept : Computer Science Engineering
Degree : B.E
SEM: : III
Website : sjbit.edu.in
Document Type : Question Bank

Download Model Question Paper : https://www.pdfquestion.in/uploads/sjbit.edu.in/3226-CSE-V-FORMAL%20LANGUAGES%20AND%20AUTOMATA%20THEORY%20%5b10CS56%5d-QUESTION%20PAPER.pdf

Formal Languages & Automata Theory Question Paper

Unit 1 :

Introduction to Finite Automata

Related / Similar Question Paper :
SJBIT BE Programming The Web Question Bank

1. Obtain DFAs to accept strings of a’s and b’s having exactly one a.(5m )( Dec-2012)
2. Obtain a DFA to accept strings of a’s and b’s having even number of a’s and b’s
3. Give Applications of Finite Automata. (5m )(Jun-July-2014)
4. Define DFA, NFA & Language? (5m)( Dec-2012)
5. Obtain a DFA to accept strings of a’s and b’s starting with the string ab. (6m )(Dec-2013) (Jun- July-2012)
6. Draw a DFA to accept string of 0’s and 1’s ending with the string 011.(4m)( Dec-2013) (Jun-July 2014)
7. DFA to accept strings of 0’s, 1’s & 2’s beginning with a 0 followed by odd number of 1’s and ending with a 2. (10m )(Dec-2013)(Jun-July-2012)
8. Design a DFA to accept string of 0’s & 1’s when interpreted as binary numbers would be multiple of 3 (5m )(Jun-July-2013, June-July-2014)
9. Find closure of each state and give the set of all strings of length 3 or less accepted by automaton.(5m)(Jun-July-2013)
10. Obtain a DFA to accept strings of a’s and b’s having a sub string aa. (5m)(Jun-July-2013)
11. Write Regular expression for the following L = { an bm : m, n are even} L = { an,bm : m>=2,(5m)(Dec-2012, Jun-July-2014)

UNIT 4 :

Context-Free Grammars And Languages

P.T. If L and M are regular languages, then so is L??M. (10m)(June-July 2012)
Write a DFA to accept the intersection of L1=(a+b)*a and L2=(a+b)*b that is for L1 ˆL2. ( 10m)(June-July 2012, Jun-July-2013)
Find the DFA to accept the intersection of L1=(a+b)*ab (a+b)* and L2=(a+b)*ba (a+b)* and that is for L1 ˆ L2 (10m)( Dec-2013, Jun-July-2014)
P.T. If L and M are regular languages, then so is L – M. ( 10m)(Dec-2012)
Design context-free grammar for the following cases(10m)(Dec-2013, June-July 2014 )
L={ 0n1n | n
L={aibjck| i?j or j?k}
Generate grammar for RE 0*1(0+1)* (10m)(June-July 2014)
P.T. If L is a regular language over alphabet S, then L = 6* – L is also a regular language. ( 8m) (Dec-Jan 2014) (Jun-July-2012)
8. P.T. – If L is a regular language over alphabet 6, then, L = 6* – L is also a regular language. ( 8m) (Dec 2012, Dec-2013)
9. P.T. If L is a regular language, so is LR ( 6m)(Dec-2012) (Jun-July-2014)
10. . If L is a regular language over alphabet 6, and h is a homomorphism on 6, then h (L) is also regular. ( 10m)(June-july- 2012).
11. Explain CGF with an example. ( 5m)(Jun-July-2014)
12. Explain decision properties of regular language. ( 5m)(Jun-July-2013)

Unit 6 :

Properties of Context-Free Languages

1. Eliminate the n->n-generating symb->ls fr->m S -> aS | A | C, A ->a, B -> aa, C – > aCb. (8m)(June 2012)
2. Draw the dependency graph as given above. A is non-reachable from S. After eliminating A, G1= ({S}, {a}, {S -> a}, S). (6m)(June 2013)
3. Find out the grammar without H – Productions G = ({S, A, B, D}, {a}, {S o aS | AB, A -> H, B-> H, D ->b}, S). (6m)(June 2014)
4. Eliminate n->n-reachable symbols from G= ({S, A}, {a}, {S -> a, A ->a}, S) (10m)(Dec-2013)
5. Eliminate non-reachable symbols from S -> aS | A, A -> a, B -> aa. (10m) (Dec-2012)
6. Eliminate useless symbols from the grammar with productions S -> AB | CA, B – >BC | AB, A ->a, C -> AB | b. (5m)(June 2014)

Unit 7 :

Introduction To Turing Machine

2. Explain with example problems that Computers cannot solve.(6m)( June- 2012)
3. Explain briefly the following Halting problem. ( 4m)(June 2013)
4. Explain Programming techniques for Turning Machines( 10m)(Dec-Jan-2010)
5. Design a Turing machine to accept a Palindrome. ( 10m)(Dec-2013)
6. Design a TM to recognize a string of the form anb2n. (10m)(Dec-2013)
7. Define undesirability, decidability. (10m)( June 2014)
8. Post’s Correspondence problem Design a TM to recognize a string of 0s and 1s such that the number of 0s is not twice as that of 1s. ( 10m) (June- 2012, Dec-2013)

Unit 8 :

Undecidability

1. Design a TM to recognize a string of the form anb2n. ( 10m) ( June- 2013)
2. P.t If L is a recursive language, L is also recursive.(10m) (June 2014)
3. Design a Turing Machine to recognize 0n1n2n. (10m)( Dec-2013)
4. Explain briefly the following Halting problem(6m)( Dec-2012, Dec-2013)
5. Post’s Correspondence problem Design a TM to recognize a string of 0s and 1s such that the number of 0s is not twice as that of 1s(10m)( Dec-2012)
7. Design a Turing machine to accept a Palindrome. ( 7m)(Dec-2013)
8. Write a short note on: (20m) Dec-2012)
a. Undesirability
b. Halting problem
c. decidability.