UGC NET CSE | June 2013 | Part 3 | Question: 36

Question

The grammar with production rules $S \rightarrow aSb \mid SS \mid \lambda$ generates language $L$ given by:

• A. $L = \{ w \in \{a, b\}* \mid n_a(w) = n_b(w) \text{ and } n_a(v) \geq n_b(v) \text{ where v is any prefix of w} \}$
• B. $L = \{ w \in \{a, b\}* \mid n_a(w) = n_b(w) \text{ and } n_a(v) \leq n_b(v) \text{ where v is any prefix of w} \}$
• C. $L = \{ w \in \{a, b\}* \mid n_a(w) \neq n_b(w) \text{ and } n_a(v) \geq n_b(v) \text{ where v is any prefix of w} \}$
• D. $L = \{ w \in \{a, b\}* \mid n_a(w) \neq n_b(w) \text{ and } n_a(v) \leq n_b(v) \text{ where v is any prefix of w} \}$

Answer 1

 S→aSb∣SS∣λ

This grammar will generate all strings in which  n_a(w) = n_b(w) .

A prefix is a string of any number of leading symbols.

For example, the string abc has prefix (empty string), a, bc, abc. When we consider the prefix v of w, the number of ‘a’s in it is either greater than or equal to ‘b’s in the string w. 

For example, aab is prefix of the string aabb. Here, number of ‘a’s is more than the number of ‘b’s. ab is a prefix of the string abab. The number of ‘a’ and ‘b’ are equal. So, when we consider the prefix v, the number of ‘a’s and ‘b’s are equal.

 

Hence,Option(A) is the Answer.

Answer 2

Ans A

• Each S produces one a and one b together only.
• For each a produced, one b will also be produced.

Hence n _a  (w)= n _b (w)

• Since before each b, one a is produced, number of a's >= number of b's for any substring.

So n _a (v) >= n _b (v)

Comments

@shiva sub string can be
bab ?
If I am right then your answer is wrong
So here b>a now it is wrong