7,079 views
23 votes
23 votes

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\}$

2 Answers

Best answer
42 votes
42 votes

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
27 votes
27 votes

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

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

edited by
Answer:

Related questions

31 votes
31 votes
2 answers
1
Kathleen asked Sep 18, 2014
10,912 views
Consider the grammar with the following translation rules and $E$ as the start symbol$$\begin{array}{lll}E \rightarrow E_ 1\# \: T & \qquad\left\{E.value = E_1.value * ...
21 votes
21 votes
2 answers
2
29 votes
29 votes
2 answers
4
Kathleen asked Sep 18, 2014
6,360 views
Consider a program $P$ that consists of two source modules $M_1$ and $M_2$ contained in two different files. If $M_1$ contains a reference to a function defined in $M_2$ ...