1
$\begingroup$

We know that $L$ = { $w$ $\in$ {a, b}* $|$ $|w|_{a}$ > $|w|_{b}$ }

This is my answer: $G$ = ({$S$,$A$,$B$},{$a$,$b$},$R$,$S$)

$R$ = S $\to$ $AB$

$A$ $\to$ $aA | Aa |B$

$A$ $\to$ $a | abB | Bab | Bba |aBb|bBa $

But after testing, it seems that writing like this is wrong.

So how should it be written?

https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

This link can be used to simulate.

$\endgroup$
2
  • $\begingroup$ Are you checked my answer? $\endgroup$
    – Jut
    Jul 14 '21 at 12:55
  • $\begingroup$ Yes, I think your answer is correct, thank you very much! $\endgroup$
    – 056040
    Jul 18 '21 at 4:47
0
$\begingroup$

Your problem is finding a CFG grammar $G$ for the language $L$ that contains equal number of $a's$ and $b's$ with extra number of $a's$ . $$L=\{\omega\in \Sigma^*\mid n_a(\omega)>n_b(\omega)\}$$

Let $A$ is a variable that derive only $a's$.

Let $E$ is a variable that derive equal number of $a's$ and $b's$.

Let $S$ be start symbol.

As a result we have the following grammar $G$:

$$S\to EAE\mid SS$$ $$E\to EE\mid aEb\mid bEa\mid \lambda$$ $$A\to aA\mid a$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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