Question

Consider the regular grammar:

S $\to$ Xa $\mid$ Ya
W $\to$ Sa
X $\to$ Za
Y $\to$ Wa
Z $\to$ Sa $\mid$ $ϵ$


Where S is the starting symbol, the set of terminals is {a} and the set of non-terminals is { S, W, Y, Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA?

• A. 5
• B. 4
• C. 3
• D. 2

Answer 1

The correct option is C 3

The given grammer after substitution of X and Y becomes

$S\to Zaa\mid Waa$
$Z\to Sa\mid ϵ$
$W\to Sa$

Which after substituting Z and W is equivalent to
$S\to Saaa\mid aa\mid Saaa$

Which is equivalent to
$S\to Saaa\mid aa.$

$So.L\left(G\right)=(aaa{)}^{\ast }aa$

So the language generated by the grammer is the set of strings with a's such that number of a mod 3 is 2. So the number of states required should be 3 to maintain the count of number of a's mod 3.