Question

This is a push down automata, what does it mean? Please explain:

0,000 0,$0 1,111 PDA M 1,$-»1 0,1A 1,0 92 91

Answer 1

$ represents the initail pushed stack symbol

so if you get a 0/1 and there is $ on top of stack then you push 0/1 respecitvely

if you get a 0 and top of stack is 1 then you remove the top element of the stack which is 1

if you get a 1 and top of stack is 0 then you remove the top element of the stack which is 0

if you get a 1 and top of stack is 1 then you add 1 to the top of the stack

if you get a 0 and top of stack is 0 then you add 0 to the top of the stack

if you see any empty string and top of stack is 1 then you remove the top of the stack.

so it says if there is 1 in the string it will be be accepted.

so the pda accepts the strings which has 1 in it.