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!

$\endgroup$
5
  • $\begingroup$ Hint: $L = a^n b^n\,bbb\,b^*$ $\endgroup$
    – Pseudonym
    May 29 at 10:51
  • $\begingroup$ @Pseudonym This gives $m \ge n+3$. $\endgroup$ May 29 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 at 12:36
  • 2
    $\begingroup$ The intended interpretation is $\bigcup_n a^nb^nbbbb^*$ $\endgroup$ May 29 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 at 23:44

1 Answer 1

2
$\begingroup$

enter image description here

$S \rightarrow aSb/A $

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

$B \rightarrow bB/\epsilon$

$\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.