1
$\begingroup$

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$

$\endgroup$
1

1 Answer 1

0
$\begingroup$

You must handle aXb and bYa sequences seperately.

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

$\endgroup$
0

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.