The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 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\}$

asked in Compiler Design by Veteran (59.7k points) | 1.1k views
S-> b then S becomes final state.

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

2 Answers

+25 votes
Best answer

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

answered by Veteran (55.6k points)
edited by
how we form 0 no's  of a
s-->b , 0 a present
If anyone face it difficult to understand then he/she can draw NFA, as given grammar is right-linear.
how?  not getting    result
+12 votes

becoz it is right linear grammer,,,so draw m/c

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

answered by Boss (11.6k points)
edited by
How come is this a DFA?

 Tuhin Dutta haha 

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.


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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,497 answers
65,748 users