context-free-grammarautomatapushdown-automatonautomaton

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

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

{ ai bj bi aj | 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 bj in-between ai and bi.

Solution

  • 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 }