1.3k views

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

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

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

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

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

0
S-> b then S becomes final state.

but how draw transition for B-> a ???
+1
No of a's divisible by 3.

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

edited by
0
how we form 0 no's  of a
+3
s-->b , 0 a present
+6
If anyone face it difficult to understand then he/she can draw NFA, as given grammar is right-linear.
0
how?  not getting    result

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

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

edited
+1
How come is this a DFA?
0

Tuhin Dutta haha

0
Sir I understand the logic of converting a linear grammar to DFA, but why do we make the productions $S \rightarrow b$ and $B \to a$ lead to a null state? Any reference will be great.
0

In right linear questions,they can be attacked by converting to machine.sometimes we dont recognize language by just looking at it,But when we get machine we can recognize easily.

Now coming to your doubt.That null was because it is a non terminal.If from start symbol we get b,it is end we cannot get anything more.And it is in language so it is accepted state

0

@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?

0

Epsilon is not in the language.

1
2