SUGGESTIONS
i) Let A={a, b}. The number of possible strings of length ‘n’ that can be formed by the elements of the set A
is __________.
ii) If an alphabet has n number of letter, then number of strings of length m will be
a) n+m
b) (n)(m)
c) m^n
d) n^m
iii) Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.
a) One
b) Two
c) Three
d) Four
iv) Languages generated by kleene star are always ______________.
a) Finite
b) Infinite
c) Sometimes finite & sometimes infinite
d) None of the these
v) What is the difference between a deterministic finite automaton (DFA) and a non-deterministic
finite automaton (NFA)?
vi) The number of tuples in a Non Deterministic Finite Automaton is ___________. vii) Let N be an NFA
with n states and let M be the minimized DFA with m states recognizing the same language. What is the necessary
relationship between m and n?
viii) What is the difference between δ (delta function) and δ^ (extended delta function)?
Group B
(Short answer type questions)
2. a) Design a DFA for the following languages over Σ={a,b}.
L={vwv: v,w ∈{a,b}*, |v|=2}
b) Design a DFA for the language accepting all strings having no more than 3 ‘a’ over input alphabet Σ = {a, b}.
c) Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets Σ = {a, b}.
3. a) Construct a minimum state automaton equivalent for the following DFA.
PS Input
0 1
🡪P Q U
Q V R
*R P R
S R V
T W U
U R V
V V T
W V R
b) Construct a minimum state automaton equivalent for the following DFA
PS Input
0 1
🡪q0 q1 q5
q1 q6 q2
*q2 q0 q2
q3 q2 q6
q4 q7 q5
q5 q2 q6
q6 q6 q4
q7 q6 q2
5. A) Consider the following DFA and answer the following:
i) Are the strings ‘aaaabb’ and ‘aabbb’ acceptable?
ii) Describe the following DFA using its 5-tuple format.
B) Consider the following DFA and answer the following:
i) Are the strings ‘aaaabb’ and ‘aabbb’ acceptable?
ii) Describe the following DFA using its 5-tuple format.
4. a) Construct DFA equivalent to the NFA M whose transition table is given below:
State/∑ Input
0 1
🡪q0 {q ,q } {q ,q }
0 3 0 1
q 1 - {q } 2
q 2 {q ,q }
2 4 {q } 2
-
q 3 {q } 4
*q 4 {q } 4 {q } 4
b) Construct DFA equivalent to the NFA M whose transition table is given below:
State/∑ Input
0 1
🡪q0 {q ,q } {q }
0 1 1
q 1 {q } 2 {q }
2
q 2 - {q }
2
