GATE CSE 2004 | Question: 88

Question

Consider the following grammar G:

$S \rightarrow bS \mid aA \mid b$

$A \rightarrow bA \mid aB$

$B \rightarrow bB \mid aS \mid a$

Let $N_a(w)$ and $N_b(w)$ denote the number of a’s and b’s in a string $\omega$ respectively.

The language $L(G)$ over  $\left\{a, b\right\}^+$ generated by $G$ is

• A. $\left\{w \mid N_a(w) > 3N_b(w)\right\}$

• B. $\left\{w \mid N_b(w) > 3N_a(w)\right\}$

• C. $\left\{w \mid N_a(w) = 3k, k \in \left\{0, 1, 2, …\right\}\right\}$

• D. $\left\{w \mid N_b(w) = 3k, k \in \left\{0, 1, 2, …\right\}\right\}$

Comments

As the grammar is a Right Linear grammar, so we can design a finite machine directly. but If it is left linear then 

Following steps:

Follow the steps:

1. Take reverse of the grammar.
2. Create Finite automata .
3. Then again take the reverse of the FA and that will be our final output.
4. Start State: It will be the first production state.
5. Final State: Take those states which end up with input alphabets.

 

Conversion of Left Linear Grammar to Finite Automata (scanftree.com)

---

Let , eqn1 is #b = y . #a =3x. Where x and y are natural nos. Substitute A and B using eqn1 .  Substitute A , B in Productions of S . We get eqn1 . This works only beacuse the grammar doesnt specify the rules for ordered set of (a,b) as a and b can occur anywhere in a word w without restriction.

---

correct me if i am wrong 

 

Answer 1

above CFG generate string $b$, $aaa$..
$b$ will eliminate options A and D
$aaa$ eliminate options B.
C is answer i.e. number of $a = 3k, k =0,1,2$....

Comments

@Sachin Mittal 1 what does right linear infer here???

---

Vaishalikashyap you can design finite automata for left linear grammar also.

Conversion of Left Linear Grammar to Finite Automata (scanftree.com)

---

@jitendra Right linear grammar means that the non-terminal symbol will be at the right side of the production.

 

Answer 2

becoz it is right-linear grammar, so draw m/c

so number of $a = 3k, k =0,1,2....$

Comments

It is not a DFA . In-state B there are two different transitions on symbol ‘a’.

---

yeah buddy

---

as it's a FA, we can already rule out option A and B as we can't do comparisions in infinite domain? (asking doubt)

Answer 3

There can be one another way to answer this question i.e.

Here, we have
S → bS
S → baA (S → aA)
S → baaB (A → aB)
S → baaa (B → a)
Therefore, | Na (w) | = 3.
Also, if we use A → bA instead of A → aB,
S → baA
S → babA
To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
S → baA
S → babA
S → babaB
S → babaa
Thus, here also, | Na (w) | = 3. So, C is the correct answer