Search code examples
automata

DPDA automata rules

I'm having trouble understanding the difference between npda vs dpda i think it goes like this

NPDA- from a state multiple choices can be taken to get to next state

DPDA- from a state, only 1 path can be taken to the next state

..but there are 2 rules concerning DPDA that i can't get a black and white understanding of

..per wikipedia enter image description here

for the first rule:

  • q is a state, a is an alphabet symbol, x is a stack symbol

what does "has at most one element" mean

I have no idea what the second rule means.

Could someone translate this into plain english please. I'd be grateful.

Solution

  • For the first rule, "has at most one element" means there is only one delta transition for a particular input and stack symbol (delta transitions are treated formally as a set for PDAs). In other words, if there is something on top of the stack and input coming in, there are never multiple states to go to.

    As you stated, "DPDA- from a state, only 1 path can be taken to the next state." This rule is the formal way of denoting that only one path may be taken.

    A violation of rule 1 might specify two delta transitions at the same state with the same input symbol and stack symbol. For example, there could be two transitions from a state q that each require a b on the stack and an a as input, but go to different states. This would not be a DPDA.

    The second rule states that if there are delta transitions for the empty string under a stack symbol, then there are no delta transitions for any letter of the alphabet under that stack symbol.

    This means that if you allow a particular stack symbol to be popped at a state without any input, you cannot allow it to also popped at that same state with input.

    A violation of rule 2 might allow popping as from the stack without any input between 2 states but also allow popping a's from the stack with a b as input.