Simple explanation of PDA accept states?

243 views Asked by At

I've been trying to find a super simple explanation of Push-Down Automaton. This is what I've come up with so far:

  1. A PDA has three operations:

    • A push to the stack; given an input state, input symbol, and the top stack symbol
    • A pop from the stack; given an input state, input symbol, and the top stack symbol
    • A "switch" operation, replacing the top of the stack with another symbol; given an input state, input symbol, and the top stack symbol
  2. A PDA has two accepting forms:

    • Operations such that the stack has been emptied
    • Operations such that the stack is back to the starting symbol, and on an accepted final state.

I'm wondering if my second point here is correct. Are these the only two ways a PDA will accept a string, and are these even correct? I've found a ton of examples, but no super simple explanation of the idea.

0

There are 0 answers