Understanding Push Down Automata

Question

I do not understand the arrows in the PDA graph...

I have a PDA that accepts all strings with parentheses nested like ((((())))), (()), ((())) etc. It has two states where the first state has an arrow that loops and the behavor of this is described as (,ε/(.

For what I could see, this description would accept the ( sign if there is an ε on the top of the stack, and if there is, the ε would be replaced with (.

So if the stack looked like this in the beginning:
ε

it looks like this now:
(ε

How can it be so that this loop arrow keep accepting every ( sign even if the ε is not at the top of the stack anymore?

Answer 1

You would need a another behavior for that state that said: (, (->( This transition should take you to another state(an auxillary state). That aux state's only transition would be ε, ε->(

From your original state you would need to pop ( off the stack when you see a ) ), (->ε

Here is a similiar example of mine that contains more a's than b's (problem number 1)