1
$\begingroup$

I've been trying for hours to figure out, how to form a CFG describing this language $L$: $$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\text{ in }\{a,b\}^* \}.$$

The problem I'm having is related to the first $n$ of $a$'s. I can't wrap my head around how can this be described properly, since the $x$ can also contain 3 $a$'s.

This is my current solution. It does not work because it doesn't take the $n$ $a$'s to the front.

A -> aB | bB
B -> aC | bC
C -> aD | bD
D -> bE
E -> bF
F -> bF | _ 
$\endgroup$
2
$\begingroup$

$S \to aSb \mid Abb, A \to aaa \mid aab \mid \ldots \mid bbb.$ That's it. First create an equal number of $a$s and $b$s with $S$. Eventually go to the $Abb$ rule creating two extra $b$s and then terminate with $A$ to any string of length $3$.

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