The Gateway to Computer Science Excellence
+15 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\}$

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

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

2 Answers

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

by Veteran (60.5k 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
+16 votes

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

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

by Boss (12.2k 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


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

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
50,647 questions
56,461 answers
100,247 users