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.
Subscribe
Login
0 Comments