Search code examples
pushdown-automaton

What is the language accepted by the PDA shown below

u

I'm not sure about my answer of this question. When I follow the question, My answer is

{a^nb^ma^n | m,n∈ N,m,n>=0}

Is this right? Can someone check my answer?

Solution

  • Suppose this PDA accepts by accepting state alone, and stack contents do not matter.

    Then it accepts all of the following:

    1. bb*, by immediately seeing a b from state 0
    2. (aa)*, by looping between states 0 and 2
    3. (a^n)b*(a^n) for n > 0 by reading n a's in states 0 and 2, then reading any number of b's in state 3, then reading n a's in state 4.

    Item 3 is what you identified, except it doesn't include the empty string. However, our item #2 includes the empty string, so you're fine on that count. So, your language doesn't contain anything NOT in the language; your language is a subset of mine.

    But my language is a subset of yours, too, since item 1 corresponds simply to all non-empty strings in your language with n = 0, and my item 2 corresponds to all strings in your language with m = 0.

    Because your and my languages are subsets of each other, they are the same, and your rendering is more compact and elegant than mine. So, we agree that you got the right answer.