Find a CFG for all words that can be obtained in the form $a^ib^{i+k}a^k$

43 Views Asked by At

Find a CFG for all words that can be obtained in the form of $a^ib^{i+k}a^k$ where $i,k\ge1$.

This is what I have so far:

$$ S\to aXa \\X\to bXB \mid bb $$

I understand that number of b's must be equal to the addition of the a's on their left and right side.

How do I approach this problem?

1

There are 1 best solutions below

3
On BEST ANSWER

Writing as $a^ib^ib^ka^k$ makes the rules obvious: $$S\to XY,X\to aXb|ab,Y\to bYa|ba$$