I am a little confused on how to approach this problem. I am unsure how to construct both parts of the grammar using a context-free grammar.

This is as far as I got, but this will end up producing a's inside of the group of b's and a's. I'm not sure how to add the second group of a's to the right of the b's.

$S \rightarrow aSb \ | \ A$

$A \rightarrow bAa \ | \ λ$

This language should produce strings like

$abba, aabbba, aaaabbbbbbaa$


You must handle aXb and bYa sequences seperately.

$\\S \rightarrow \ XY\ |\ \epsilon \ \\ X\rightarrow \ aXb\ | \ \epsilon \\ Y\rightarrow \ bYa\ | \ \epsilon$


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.