0

These are transitions for a push down automata. ((p, a, ϵ),(q, γ)) is equivalent to, if in state p, reading input a, do nothing to the stack, transition to state q, push γ on to stack.

1. ((p, a, ϵ),(q, γ))

((p, ϵ, A),(q′, γ′))

Both transitions apply if the state is p, reading an a, and A is on top of the stack

2. ((p, a, A),(q, γ))

((p, a, AB),(q′, γ′))

Both transitions apply if the state is p, reading an a, and AB is on top of the stack

3. ((p, a, A),(q, γ))

((p, ϵ, AB),(q′, γ′))

Both transitions apply if the state is p, reading an a, and AB is on top of the stack

I get why 1 would be non deterministic, but I'm not sure how 2 and 3 are non deterministic. An a (or ϵ) is read, and an A or AB is popped off the stack. But the rules suggest that either A or AB can be on top of the stack, when one of the transitions only call for the removal of an A.

I am reading it like, for the transition (p, a, A),(q,y), if we are in state q, have an input a, and an A "can" be removed from the top of the stack, then we can transition to state q and push a y on to the top of the stack. So it seems to me that

((p, a, A),(q, γ))

((p, a, AB),(q′, γ′))

are distinct, as in, deterministic, because they represent two separate cases for a transition to (q, y). It doesn't seem like there's any "guessing" involved.

pajkatt
  • 373
  • Some context, and explanation of notation, might be helpful. – Robert Israel May 05 '17 at 22:22
  • @RobertIsrael added, not sure if enough. I think I might just be misunderstanding PDA transitions – pajkatt May 05 '17 at 22:26
  • In case 2, if the stack is $ABCD$, you can transition to either state $q$ (with a stack of $\gamma BCD$) or to state $q'$ (with a stack of $\gamma'CD$). – Steven Stadnicki May 05 '17 at 22:50
  • Ah, so AB is not considered a single symbol, but rather just remove A and then B. And in this case, if there is an A on top of the stack, we can choose to transition to either state q or q' even if there is a B next? – pajkatt May 05 '17 at 22:56
  • (I may be misreading your notation, but the same principle still holds - you can transition to either state $q$ or state $q'$.) – Steven Stadnicki May 05 '17 at 22:56
  • 1
    @pajkatt It's your notation! It certainly doesn't seem like $AB$ is considered to be a single symbol, though. as there's no reason for the confusion with $A$ as a symbol. – Steven Stadnicki May 05 '17 at 22:57

0 Answers0