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

@Swati Rauniyar  yes ,you can write

(PQ)*P=P(QP)*.let P=aa ,Q=a

then (aaa)*aa=aa(aaa)*

---

because of only one terminal symbol a, L and L reversal would be same only.

---

Just substitute ..I think its easy.

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

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 :

A-->aB/bA/b

B-->aC/bB

C-->aA/bC/a

so here how to determine the final state .

---

A-->aB/bA/bF

B-->aC/bB

C-->aA/bC/aF

F-> ∊

 

---

"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 :
A-->aB/bA/b
B-->aC/bB
C-->aA/bC/a
so here how to determine the final state ." @radha gogia

The Non-terminal which derives a terminal directly is marked as the final state because they can produce a terminal symbol which is considered to be the basic element of any string

---

@ Praveen sir, Why was it required to convert the grammar to right linear?

---

There are two ways to solve the given problem.

1. find the language from given left/right linear grammar, Draw the dfa for language and minimize it.

2. Covert the given left linear grammar to right linear grammar. bcoz we can easily find the transitions of a FA corresponding to production of right linear grammar.

A$\rightarrow$ aB is equivalent to transition $\delta (A,a) = B$

In solution I did as per 2nd approach.

---

excellent sir

---

Thank You Sir.

---

your approach for finding RLG from LLG does not work always..

refer https://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars#

provided by shreshta

---

Sir how do we know which is final state from given regular grammar of nfa?

---

Since, the input symbol is $\sum=\{a\}$, $L=L^R$ and so on reversing the productions of the given grammar, the grammar we get is the right linear grammar for the same language L.

---

@Praveen Saini i am not getting, how do we know which one is final state in nfa? and sir how do you know that "Z" Is Final State In 1st NFA ?

 

---

@radha gogia @Praveen Saini

A will be the final state. 

---

If we draw a NFA according to Given Grammar i.e. Left Linear Grammar, then we say that Starting State is one having $\epsilon$ in the production. My doubt is How we are going to find Final State?

---

why can't we make a NFA from Left linear grammer

---

i think answer should be c. becozin dfa we also make a dead state

---

@sandmuk754 But why do you need a Dead state?

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

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

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