1. Any NFA having n states can be converted to a DFA having at most (select the smallest possible value)
- 2n
- 3n
- 2n
- n2
Answer :- a
2. Consider the language L={w∣the number of 1’s in w is divisible by 3} over the binary alphabet {0,1}. What is the minimum number of states required for a DFA that accepts L?
- 1
- 2
- 3
- 4
Answer :- c
3. What is the ϵ-closure of state q1 in the following NFA?
- {q0,q1,q2}
- {q0,q1,q2,q3}
- {q0,q1}
- {q1}
Answer :- c
4. Which of the following strings is accepted by the DFA below?
- 01011101
- 00111100
- 10100011
- 11000010
Answer :- a
5. Let L1 and L2 be two regular languages. What can we say about the language L={w1w2∣w1∈L1,w2∈L2}?
- L may or may not be regular
- L is regular
- L is not regular
- L is accepted by some NFA but there is no DFA that can accept L
Answer :- b
6. What is the language accepted by the following NFA?
- {w∈{0,1}∗∣w ends with 0 and begins with 1}
- {w∈{0,1}∗∣w begins with 0 and ends with 1}
- {w∈{0,1}∗∣w ends with 0 or begins with 1}
- {w∈{0,1}∗∣w begins with 0 or ends with 1}
Answer :- d
7. Consider the language
L={w∈{0,1}∗∣w begins with 00}
How many states will the minimal DFA for L have?
- 2
- 3
- 4
- 5
Answer :- c
8. Consider the following DFA.
What is the language accepted by this DFA?
- {w∈{0,1}∗∣w has exactly one 1}
- {w∈{0,1}∗∣w ends with a 1}
- {w∈{0,1}∗∣w begins with a 1}
- {w∈{0,1}∗∣w consists of only 1’s}
Answer :- b