Finding a grammar or a pushdown automaton that recognizes { a^i b^j b^i a^j | i,j >= 0 }

Question

I am trying to find either a grammar or a pushdown automaton that recognizes the following language:

{ aⁱ b^j bⁱ a^j | i,j >= 0 }

Of all the examples that I have seen, I cannot wrap my head around this one!

I first tried using a grammar for it as I think this may be easier recursively, and then a pushdown automaton, with no luck. I don't know what to do with the b^j in-between aⁱ and bⁱ.

Answer 1

Just as i + j = j + i, bibj = bjbi. In other words, two b's are indistinguishable from each other.

Perhaps you will find it easier to see the grammar for { aibibjaj | i,j ≥ 0 }