1
$\begingroup$

Can you to find for me a context free grammar for the following language?

$$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$

Here $\#_a(w)$ counts the number of $a$'s in $w$.

$\endgroup$
1

2 Answers 2

4
$\begingroup$

Let $c(w)=2\#_b(w)-\#_a(w)$. Your language is exactly $\{w\mid c(w)=0\}$.

Now consider a string $w$ with $c(w)=0$ and $|w|\ge 2$. If we can split $w$ into three parts: $w=pms$ such that $c(p)$ and $c(pm)$ have different signs, i.e., $c(p)c(pm)<0$, then there are two cases:

  1. $c(p)>0$ and $c(pm)<0$. Note each time we append a character to string $x$, $c(x)$ is either increased by 2 or decreased by 1, so we can always split $m$ into two parts $m_1m_2$ such that $c(pm_1)=0$.

  2. $c(p)<0$ and $c(pm)>0$. In this case we can always split $m$ into two parts $m_1m_2$ such that either $c(pm_1)=0$, or $c(pm_1)=-1$ and $m_2$ begins with $b$.

As a result, either $w=w_1w_2$ where $c(w_1)=c(w_2)=0$, or $w=w_1bw_2$ where $c(w_1)=c(w_2)=-1$.

If $w$ cannot be split into such three parts, then $w$ must be either $bw_1aa$ or $aaw_1b$ where $c(w_1)=0$.

So, if we let $S_-$ generate the language of strings where $2\#_b-\#_a=-1$, then we have the following grammar \begin{align} S&\rightarrow SS\mid S_-bS_-\mid bSaa\mid aaSb\mid\epsilon\\ S_-&\rightarrow aS\mid SS_- \end{align}

$\endgroup$
1
  • $\begingroup$ Is the obtained grammar unambiguous? If yes, how can we prove it? $\endgroup$ May 1, 2021 at 23:22
1
$\begingroup$

The following grammar generates the language $L = \{ w \in \{a, b\}^*\ | \ \#_a(w) = 2\#_b(w) \}$.

S -> bSaa | baSa |
     aSba | abSa |
     aSab | aaSb |
     SS | ε

First, for every b introduced, 2 a's are introduced. The location of an b could be before, between, or after both a's.

Aside for the rule S -> SS, the grammar generates the string from outside in. Thus, there is no left or right recursion. So there are two places in each rule where recursion could happen: inside on the left and inside on the right.

Suppose there is a string $w = bxb \in L$. An example of such a string would be baaaab. Since $\#_a(w) = 2\#_b(w)$, then $\#_a(x) = 2(\#_b(x) + 2)$. There must exists at least one point in $x$ such that $x = x_1x_2$ where $bx_1 \in L$ and $x_2b \in L$. Hence the rule S -> SS.

Edit: The following rules must be added. See the accepted answer for a complete solution. These rules allows us to build string from inside out.

S -> QbQ
Q -> aS | SQ
$\endgroup$
3
  • $\begingroup$ No, it doesn't. It generates the language $L = \{a^ib^{2i}\mid i\ge 0\}$. $\endgroup$
    – rici
    Aug 5, 2020 at 23:04
  • 1
    $\begingroup$ I've edited my solution. First a misunderstanding between $\#_a(w) = 2\#_b(w)$ and $2\#_a(w) = \#_b(w)$ and an oversight of where symbols can be located (i.e. it's not necessary for all a's to be followed by all b's). $\endgroup$
    – tylerh111
    Aug 6, 2020 at 1:22
  • 1
    $\begingroup$ Your grammar seems not to generate $aaabbbaaa$. $\endgroup$
    – xskxzr
    Aug 6, 2020 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.