-1
$\begingroup$

The thing that confuses me here is that i've seen a similar example where $L=\{a^nb^m : 2m\leq n\leq 4m\}$ where the CFG was straight forward: $$ S\rightarrow aSbb\\ S\rightarrow aSbbb\\S\rightarrow aSbbbb\\S\rightarrow \epsilon $$ however, in this example I cant get my mind out of the "just go for the simple approach" which is $$ S\rightarrow aSbbb\\S\rightarrow\epsilon $$ however this feels somewhat incomplete to me.

EDIT: I see my errors, i propose this solution: $$ S\rightarrow aaaAb\\A\rightarrow aaaAb\\A\rightarrow \epsilon $$ this seems more correct due to the fact that now I am 'forcing' 3 $a$'s each time a $b$ shows up, also $\epsilon$ is no longer included.

$\endgroup$
5
  • 1
    $\begingroup$ I think you swaped the roles of $n$ and $m$ in the condition of the language. $\endgroup$
    – Nathaniel
    Feb 20 at 17:33
  • $\begingroup$ @Nathaniel Indeed, It seems that I've misread the language definition, I have fixed my solution. $\endgroup$
    – Aishgadol
    Feb 20 at 17:44
  • $\begingroup$ Please include the question in the body of your question. The title should help people find this page via search, but is not a replacement for stating the question in the body of the post. $\endgroup$
    – D.W.
    Feb 20 at 17:51
  • $\begingroup$ Please don't use "EDIT:". Please revise your question so it reads well for someone who encounters it for the first time, then flag comments as 'no longer needed'. See cs.meta.stackexchange.com/q/657/755. I encourage you to revise your question accordingly. I have given you similar feedback before: cs.stackexchange.com/questions/160059/#comment334941_160059 $\endgroup$
    – D.W.
    Feb 20 at 17:54
  • $\begingroup$ Please don't edit your question in a way that invalidates existing answers. If you discover that you asked the wrong question, then please take that as a lesson to exercise more care in the construction of your questions in the future, to proof-read them to make sure you are asking what you want to ask, and ask a new question. $\endgroup$
    – D.W.
    Feb 20 at 17:55

2 Answers 2

2
$\begingroup$

The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \{a^nb^m\mid 2m < n < 4m\}$, but words in $L$ like $aaaaabb$ cannot be generated by your grammar.

You can use the example grammar to construct the wanted grammar by noting these facts:

  • for each $b$, one must add $2$, $3$ or $4$ $a$'s;
  • one must neither always add $2$ $a$'s, nor always add $4$ $a$'s.
$\endgroup$
2
  • $\begingroup$ So a first rule $S\rightarrow aaaAb$ followed by the second rule $A\rightarrow aaAb | aaaAb | aaaaAb | \epsilon $ should be the right approach? $\endgroup$
    – Aishgadol
    Feb 21 at 14:32
  • 1
    $\begingroup$ @Aishgadol yes, that should do the trick. $\endgroup$
    – Nathaniel
    Feb 21 at 14:49
1
$\begingroup$

No. The grammar you propose is not correct. For example it generates $\varepsilon$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that the generated words have at least as many $b$s than $a$s, yet all words in the language have more $a$s than $b$s.

$\endgroup$
1
  • $\begingroup$ I've edited my solution, I see how I've misread the language definition. $\endgroup$
    – Aishgadol
    Feb 20 at 17:42

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.