Context Free Grammar for the language?

99 Views Asked by At

Give CFG for $L = \{w \in \{a, b\}^{*} | n_{a}(w) \leq n_{b}(w) ≤ 2n_{a}(w)\}$, here $n_{x}(w)$ is the number of occurrences of x in w.

I came up with

$S-> aSb | bSa| b$

but not working as expected. Can somebody please help. Thanks in advance..!!

1

There are 1 best solutions below

0
On BEST ANSWER

Start with a grammar for equal number of each $$ S \rightarrow a S b S \mid b S a S \mid \epsilon $$ Now see how to add another $b$ for each $a$, sometimes.