GATE IT 2005 | Question: 39

Question

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?

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

Comments

to convert left linear to right linear, we need to reverse the sting and change the place

---

how can you combine state Z and W , when state Z is a final state and W is a non final state , i think they can never be equivalent

 

---

S -> Saaa|aa

hence L = {aa, aaa, aaaa, aaaaa, .....} = a^k : k>=2

for such L 3 state DFA required.

Answer 1

• $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$

Comments

@ayushsomani the final state we make on terminals means if in the production rule there will not be variable then we can diff state to termianls ..

 

---

sir here i have a doubt that final and non-final state can never be merged because they are fundamentally distinguishable, but in this final and non-final  are merged

---

@Praveen Saini how can we combine state Z and W , when state Z is a final state and W is a non final state , i think they can never be equivalent 

Answer 2

(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.

Comments

@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

Answer 3

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]

Comments

This approach may not work if there is a dead state possible from any state, here for this question it yield correct answer since there is no dead state...

---

If there is a dead state then we can put another variable in place of S in rhs.

Then from that variable we can go to dead state by seeing strings which are not in the langiage..

---

then how could we know beforehand that this grammar is going to yield dead state or not without converting into dfa.

---

By minimizing grammar we know that what the language is...right?

If there is any string which does not satisfy grammar then we have to draw a dead state..

For example-- if Σ={a,b} and grammar implies that all strings starting with 'a' (as we try to get the language generated by G) then we put a dead state for strings starting with 'b'.

 

May be i'm not getting what you tried to ask..😑

---

the approach u hv suggested is completely fine when grammar is DFA but if it is NFA grammar like above question then we can't determine there is going to be any dead state or not without converting it to DFA or DFA grammar.

am I right?

---

No grammar is for DFA or NFA specifically. Whatever a DFA can do, an NFA can do too.
This approach works.

And as for your doubt about the dead state — it is a property of the machine (DFA or NFA) not the grammar. This approach is fine. It's grammar minimisation but keeping all its characteristics intact.

---

It is possible to remove all null and unit and useless productions to reduce the grammar and hence DFA can be construced easily!

---

Best method from exam POV.

Answer 4

GRAMAR SIMPLIFIES 

Comments

correct approach

Answer 5

Using the concept of indistinguishability/equivalency of states and merging them

Comment if there is something wrong with this approach

Comments

why u made 2 accepting states in in first digram i think its mistake

Answer 6

If you carefully decode the grammar you will get :

S-> Zaa I Waa where Z can be replaced while epsilon or Sa while W can be replaced by Sa only

Hence the minimum possible string is aa ie., two a's must be there.

So, Min DFA will have 3 states while a given DFA can have any number of states as they're not unique but Minimal DFA is unique hence only 3 states possible for it