1
$\begingroup$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$

where $n,m \ge 0$

I'm very new to this so this example might be a little harder, but everything I try I end up not finding the correct solutions. Some example strings are $\epsilon$, $a$, $aa$, $aaa$, $b$, $ab$, $aab$, $aaab$, $aaaab$, $bb$, $abb$, $aabb$, $aaabb$, $aaaabb$, $aaaaabb$ etc.

This is how I tried reasoning:

since there can be a loop of $a$ in the beginning, I thought that one production could be

$A \rightarrow aAb | \epsilon$

But this is as far as my reasoning goes. What's confusing is that for each value of $m$, I have increasing $n$.

Can anyone give a hint, or give general hints how to construct CFG from languages?

Thanks!

Improve this question
$\endgroup$
5
  • $\begingroup$ Hint: $L = a^n b^n\,bbb\,b^*$ $\endgroup$
    – Pseudonym ♦
    May 29, 2022 at 10:51
  • $\begingroup$ @Pseudonym This gives $m \ge n+3$. $\endgroup$
    – Yuval Filmus
    May 29, 2022 at 12:26
  • $\begingroup$ @YuvalFilmus Is that supposed to be a regular expression? Since we have $a^nb^n$ and $b*$ combined what is the difference between, say, $b^n$ and $b*$ in this regexp? $\endgroup$
    – john doe
    May 29, 2022 at 12:36
  • 2
    $\begingroup$ The intended interpretation is $\bigcup_n a^nb^nbbbb^*$ $\endgroup$
    – Yuval Filmus
    May 29, 2022 at 12:36
  • $\begingroup$ @YuvalFilmus Ah, yes, sorry. Even though I got it the wrong way around, the hint stands as a hint. $\endgroup$
    – Pseudonym ♦
    May 29, 2022 at 23:44

1 Answer 1

Reset to default
2
$\begingroup$

enter image description here

$S \rightarrow aSb/A $

$A \rightarrow \epsilon/a/aa/aaa/B$

$B \rightarrow bB/\epsilon$

Improve this answer
$\endgroup$

Your Answer

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

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