Expected Questions
Name: Automata Theory Code: PC 504 IT Faculty: J. Sowjanya
Short Questions:
1. Define DFA, NFA and Define Language of DFA & NFA. Give any 2 applications of FA
2. Distinguish between DFA and NFA and NFA and ε - NFA
3. Design a DFA to accept
a. odd number of 1’s and even number of 0’s over {0,1}.
b. L = { (ab)n | n > 1 }
c. L={ anbm | n, m >=1}
d. set of all strings with 3 consecutive 1’s
e. strings starting with 01 and contain even length strings DFA=({q1,q2,q3,q4,q5},{0,1},δ,q1,{q3})
f. strings of a’s and b’s of length atmost 2
4. Draw the transition diagram for a DFA with following transition table: and give the language of the DFA
δ 0 1
→q0 q2 q1
*q1 q1 q1
q2 q2 q1
5. Draw the NFA for regular expression
a. All the strings containing 01 as substring over {0,1}
b. 3rd symbol from RHS is ‘a’ over {a,b}
6. What is an Epsilon-Closure of a State? Give an example.
7. State the algebraic laws of regular expressions.
8. List the closure properties of regular language.
9. Draw the ε -NFA for regular expression
a. (a+b)*ab(a+b)*
b. (a + bb + c*)
10. Write a RE denoting strings that begins and ends with a different letter over ∑= {a,b}. i.e., if it
begins with ‘a’ then ends with ‘b’ and if it begins with ‘b’ then end with ‘a’.
11. Define Homomorphism. Give an example.
12. Give a formal definition of CFG and write a grammar for productions of palindromes over alphabet {0,1 }.
13. Define Parse tree, with an example. Define left most and right most derivation.
14. Write the CFG for RE a) 0*1(0+1)* b) 11(0+1)*0
15. When is a CFL said to be inherently ambiguous. State the reasons for Ambiguity and how do you remove
ambiguity from grammar.
Long Questions:
1. Prove a Language L accepted by some DFA can also be accepted by an equivalent NFA.
2. Write subset construction method and Convert the following NFA to DFA by subset construction method.
a.
δ 0 1
→q0 q0 {q0,q1}
q1 q2 q2
*q2 φ φ
b.
3. Convert the ε- NFA to an equivalent DFA by eliminating ε- transitions
4. Convert the following ε – nfa to nfa
5. Convert the DFA given below to regular expression, R133 using (10)
Rkij = RK-1ij + RK-1ik(RK-1 kk)*RK-1kj. Show detailed working steps in Basis and Induction.
δ 0 1
→q1 q2 q1
q2 φ q3
*q3 q3 q2
6. Convert the following DFA to RE using state elimination technique
0 1
→*P S P
Q P S
R R Q
S Q R
7. Convert given FA to regular expression using Arden’s theorem.
q0 q1
1
0 1
1 0
q2 q3
0,1
8. Obtain a regular expression for the language
a. L={anbm / m >= 1, n >= 1, nm >= 3}
b. Strings of odd length over {0,1}
9. Demonstrate minimization of DFA for the DFA given below using Table –Filling algorithm.
States 0 1
→A B F
B G C
*C A C
D C G
E H F
F C G
G G E
H G C
10. Illustrate the following:
1) if L and M are regular languages, then so is L Λ M.
2) If L is a regular language, then so is L*.
3)Give an example to show that complement of Regular Languages is not Regular.
11. State and prove pumping Lemma for regular languages and
a. show that L= {anbn | n>=1 } is not regular.
b. Show that L= {an |n=K2 for k>=0 } is not regular.
12. Test whether the following grammar is ambiguous or not
a. E→I, E→E*E, E→E+E, E→(E), I→a | b
b. SaB | bA, AaS |bAA |a, BbS |aBB |b
13. Given CFG G={(A,B),{0,1},P,A} where p={A->0BA|0, B->A1B |AA | 10}. Give RMD,LMD and parse tree for
the string “001100”. Obtain CFG to generate string consisting of any number of a’s and b’s with at least
one a.
