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

S-> b then S becomes final state.

but how draw transition for B-> a ???

---

No of a's divisible by 3.

---

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)

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

@pawan  you are defining B on 'a' to start and final 

so what if when you make start state as final state? It is also same DFA right?

---

@Suneel Padala

Epsilon is not in the language. 

---

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