Aptitude Overflow
+8 votes

Consider the regular grammar:

S → Xa | Ya
X → Za
Z → Sa | ϵ
Y → Wa
W → 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
asked in Theory of Computation by (19.4k points)  
edited by | 680 views
it contains r.e as (aaa)*aa   for that we need  3 state which is min
Would the answer be wrong if I write L= aa(aaa)* ?

2 Answers

+13 votes
Best answer

S → Xa | Ya
X → Za
Z → Sa | ϵ
Y → Wa
W → Sa

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

S → aX | aY
X → aZ
Z → aS | ϵ
Y → aW
W → aS 

is right linear grammar having language LR.  

having NFA 

Having DFA for language LR

DFA for language L ( reversal)

L = { w : na(w)mod3 =2 , w belong to {a,b}* }   same as Omesh Pandita answered 

having 3 states 

answered by (53.1k points)  
selected by
R: - 1
Sir , here it was quite easy to see that Z will be final state but in general what is the way to determine which non-terminal should be made as final state, e.g. if the grammar given is :




so here how to determine the final state .




F-> ∊


+9 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.
answered by (2.7k points)  
S -> Ya productions for Y and W are redundant? The same are done by X and Z productions rt?
Yes, they are redundant.

@Omesh, @Arjun: Set of alphabets contain only symbol  { a } .

I guess you have incorrectly included 'b' in the productions !!

If Z->b is replaced with Z->a , we need minimum 4 states as

L(G)= n(a) =3 *K   ,K>=1

Yes. It was a typo in question, now corrected. It is epsilon and not b.

@Omesh >> It should be (B) 3 and not (D) 3

Related questions

2,455 questions
849 answers
15,474 users