edited by
12,001 views
64 votes
64 votes

Consider the regular grammar:

  • $S \rightarrow Xa \mid Ya$
  • $X \rightarrow Za$
  • $Z \rightarrow Sa \mid \epsilon$
  • $Y \rightarrow Wa$
  • $W \rightarrow Sa$

where $S$ is the starting symbol, the set of terminals is $\{a\}$ and the set of non-terminals is $\{S, W, X, 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?

  1. $2$
  2. $3$
  3. $4$
  4. $5$
edited by

4 Answers

Best answer
94 votes
94 votes
  • $S \rightarrow Xa \mid Ya$
  • $X \rightarrow Za$
  • $Z \rightarrow Sa \mid \epsilon$
  • $Y \rightarrow Wa$
  • $W \rightarrow Sa$

This is left linear grammar having language L. Convert it into right linear using following rule:

  • $V_i \to V_jw \qquad \text{Reverses to}\qquad V_i \to w^RV_j$
  • $V_i \to w \qquad \quad\text{Reverses to}\qquad V_i \to w^R$

If the left linear grammar produced language $L$ then the resulting right linear grammar produces $L^R.$

  • $S \rightarrow aX \mid aY$
  • $X \rightarrow aZ$
  • $Z \rightarrow aS \mid \epsilon$
  • $Y \rightarrow aW$
  • $W \rightarrow aS$

is right linear grammar having language $\mathbf{L^R}$.  

Having NFA

Having DFA for language $\mathbf{L^R}$

DFA for language L ( reversal)

$\mathbf{L = \{ w : n_a(w) \ mod \ 3 =2 ,\text{ w belongs to } \{a,b\}^* \}}$  same as Omesh Pandita answered.

Having 3 states.

Correct Answer: $B$

edited by
21 votes
21 votes
(B) 3

The string generated by the language 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.
10 votes
10 votes
Minimize the grammer as much as you can. (Putting the values of lower productions to upper one).

Then finally we get

S→aa∣Saaa

Now we can draw dfa with 3 states.

[it may be an informal approach but we get answer fast]
Answer:

Related questions