GATE 2011 CS (CS1) – Question 52

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

Over alphabet {a}, $L=\{a^{nk}:k>0\}$, with fixed positive integer n. Find the smallest DFA state count.

k+1
n+1
$2^{n+1}$
$2^{k+1}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) n+1

Explanation

The DFA must accept positive multiples of n but reject ε. Use n residue states after reading input, accepting residue zero, and an extra initial rejecting state with the same subsequent transitions as residue zero. These states are pairwise distinguishable by suffix length or empty-word acceptance. Thus n+1, B.

More Regular Expressions and Finite Automata questions

GATE 2011 CS (CS1) Q55 – DFA D has transitions p:a→s,b→q; q:a→t,b→r; r loops on a,b; s,t are accepting and each…
GATE 2010 CS (CS1) Q49 – Which regular expression denotes all binary strings with an even number of ones?
GATE 2010 CS (CS1) Q51 – Let w be any binary string of length n, and L the set of all its substrings. What is the…
GATE 2015 CS (CS2) Q45 – Find the number of states in the minimal DFA for (0+1)*(10).
GATE 2015 CS (CS2) Q60 – Over 0,1, λ denotes the empty string. A regular grammar satisfies X0=1X1, X1=0X1+1X2,…
GATE 2015 CS (CS3) Q32 – Over Σ=0,1, let L be represented by Σ*0011Σ*. Find the minimum DFA-state count for its…

All Regular Expressions and Finite Automata questions →