Theory-of-Computation
January 3, 2025GATE 2011
January 3, 2025GATE 2011
| Question 31 |
Definition of a language L with alphabet {a} is given as following.
L = {ank| k>0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
| k+1 | |
| n+1 | |
| 2n+1 | |
| 2k+1 |
Question 31 Explanation:
Given that n is a constant.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a’s except ‘ε’.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a’s except ‘ε’.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.
Correct Answer: B
Question 31 Explanation:
Given that n is a constant.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a’s except ‘ε’.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.
So lets check of n = 2,
L = a2k, k>0
Since k>0 than zero.
So L is the language accepting even no. of a’s except ‘ε’.
So DFA will be,
So, no. of states required is 2+1 = 3.
So for ank, (n+1) states will be required.