Exam tomorrow and the prof let us know a question that would be on it :).
In the context of this diagram, L is epsilon (The empty string), and Z0 is the stack empty symbol.
I've made some progress in determining a few rules about the words the language generates, but haven't been able to pin down the entire language.
Thanks!
This PDA is not nearly as non-deterministic as it appears at first glance... Consider the following cases.
Suppose the input starts with ab. Then we go to state 2 with an empty stack, so the "L" rule does not match, so we are only in state 2.
Suppose the input starts with (a^n)b for n > 1. Then we go to state 2 with a^(n-1) on the stack, and the "L" rule triggers taking us back to state 1 with a^(n-2) on the stack. But since the stack in state 2 is a^(n-1) (and n>1), the loop-back arrows on state 2 cannot match... So here again, we are (effectively) only in one state: state 1.
Suppose the input starts with ba. Then again we go to state 2 with an empty stack, and as in case (1), the "L" rule does not match so we are only in state 2.
Finally, suppose the input starts with (b^n)a for n > 1. Then we go to state 2 with with b^n on the stack, so the "L" rule does not trigger and we are only in state 2.
In other words, any time the "L" rule creates a "fork" of the PDA into state 1, it only does so because "a" was on top of the stack... Which implies that the fork remaining in state 2 must die on the very next input symbol. So in effect there is no non-determinism here, and you can model this PDA as if it is always in just one state.
With this observation in hand, I think it is pretty easy to see that @Nayuki is correct: This PDA accepts any string with twice as many a's as b's.
First, show that when the PDA is in state 1, the stack always consists entirely of a's or entirely of b's (or is empty). And when the PDA is in state 2, the stack consists entirely of b's (or is empty). This is a simple case analysis similar to the four cases above; e.g. "state 1, stack=a^n, next character b => state 1, stack=a^(n-2)". (Taking care for the cases of n=0 or n=1.)
Think of each b as "wanting to be partnered with 2 as". State 1, stack=a^n means n as are waiting for partners. State 1, stack=b^n means n bs are waiting for partners. State 2, stack=b^n means one b was partnered with one a and n bs are still waiting for partners.
Prove that what I just wrote is true, and the result follows.
Playing with some test cases in my head and not proving anything rigorously, I think there exists an accepting computation for this (non-deterministic) PDA if and only if the input string has twice the number of a's compared to the number of b's.
Number of 'a' is twice the number of 'b's.
Exact Grammar:
S = (a|b)* where N_a(S)=2*N_b(S)
N_a(X) means Number of 'a's in X. etc.
At any point in time, the stack can either be all 'a's or all 'b's. Why? because, there are no transitions of a/xxbxx or b/xxaxx.
Case 1: Stack is all 'a's.
You can see cycle will be of the form:
a(a*b)+ , if last we take the transition L,a/L in (2->1)
a(a*b)+a, if last we take the transition a,Z0/Z0 in (2->1). and the last 'a' will not pop anything from stack.
in each cycle, the number of 'a's popped are two. and number of cycle is same as number of 'b' (except when a,Z0/Z0 occured at the last)
we'll take the last transition L,a/L iff number of 'a' is even before last 'b'
we'll take the last transition a,Z0/Z0 iff number of 'a' is odd before last 'b'. a,Z0/Z0 accepts one more 'a'
Thus,
A1=a(a*b)+a where N_a(A1)=2*N_b(A1), N_a(A1) is even
A2=a(a*b)+ where N_a(A2)=2*N_b(A2), N_a(A2) is even
This will reduce to:
A=a(a|b)+ where N_a(A)=2*N_b(A), N_a(A) is even
(we'll be state 1, and stack empty)
Case 2: Stack is all 'b's.
Similarly, you can see that each cycle will be of the form: b*ab*a. and in each cycle, exactly one 'b' will be popped off. Whenever a 'b' is accepted, a 'b' is pushed onto the stack. Thus when the stack is empty, and we're back to state 1, number of times the cycle is taken is equal to number of 'b's we accepted/pushed onto stack.Thus,
B=b(b*ab*a)^n where N_b(B)=n
But you can see, n = N_a(B)/2. Thus,
B=b(b*ab*a)+ where N_a(B)=2*N_b(B)
This will reduce to:
B=b(b|a)+ where N_a(B)=2*N_b(B)
And since there are only two possible paths (A or B), and the cycle can be taken 0 or 1 times,
Thus,
S=(A|B)*
A=a(a|b)+ where N_a(A)=2*N_b(A)
B=b(b|a)+ where N_a(B)=2*N_b(B)
This will reduce to:
S=((a|b)+)* where N_a(S)=2*N_b(S)
which will reduce to:
S=(a|b)* where N_a(S)=2*N_b(S)
Q.E.D.
