What language is this Pushdown Automata (PDA) accepting?

Question

Exam tomorrow and prof let us know the question that will be on it :).

In the context of this diagram, L is epsilon (empty string), and Z0 is the empty stack symbol.

I made some progress in defining several rules about the words that the language generates, but I could not bind the whole language.

Thanks!

Answer 1

This CCP is not as non-deterministic as it seems at first glance ... Consider the following cases.

• Suppose input starts with ab . Then we go to state 2 with an empty stack, so the rule “L” does not match, so we are only in state 2.

• Suppose that 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 rule “L” returns 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 backward loop arrows in state 2 cannot coincide ... So, again, we are (efficiently) in only one state: state 1 .

• Suppose input starts with ba . Then we go to state 2 with an empty stack, and, as in case (1), the rule “L” does not match, therefore 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 b^n on the stack, so the rule “L” does not start, and we are only in state 2.

In other words, at any time when the rule “L” creates a PDA “plug” in state 1, it only does this because “a” is on top of the stack ... It follows that the plug remaining in state 2 must die on the next input character. Thus, in reality, there is no determinism here, and you can model this CCP as if it is always in the same state.

With this observation in hand, I think it’s pretty easy to see that @Nayuki is correct: this PDA accepts any line with twice as many a than b.

First, show that when the PDA is in state 1, the stack always consists entirely or completely of b (or is empty). And when the PDA is in state 2, the stack is completely composed of b (or empty). This is a simple case analysis similar to the four cases above; for example, "state 1, stack = a ^ n, the next character b => state 1, stack = a ^ (n-2)". (Taking care of cases n = 0 or n = 1.)

Think of each b as a “desire to be a partner 2 a s”. State 1, stack = a^n means that n a waiting for partners. State 1, stack = b^n means that n b are waiting for partners. State 2, stack = b^n means that one b was a partner of one a and n b is still waiting for partners.

Prove that what I just wrote is true, and the result follows.

Answer 2

Playing with some test cases in my head and not proving anything strict, I think that for this (non-deterministic) PDA there is an acceptable calculation if and only if the input string has twice as many numbers as b .

Answer 3

The number a is twice the number b.

Exact Grammar:

 S = (a|b)* where N_a(S)=2*N_b(S) 

N_a (X) means Number of a in X. etc.

At any given time, the stack can be either "a" or "b". What for? because there are no transitions a / xxbxx or b / xxaxx.

Case 1: The stack is everything.

You can see that the cycle will look like:

• a (a * b) +, if the latter takes the transition L, a / L to (2-> 1)

• a (a * b) + a, if in the latter case we take the transition a, Z0 / Z0 in (2-> 1). and the last "a" will not delete anything from the stack.

in each cycle, the number "jumped out" two. and the number of cycles is the same as the number "b" (except when a, Z0 / Z0 occurred last)

take the last transition L, a / L, if the number "a" is before the last "b"

take the last transition a, Z0 / Z0, if the number 'a' is odd until the last 'b'. a, Z0 / Z0 accepts another "a"

In this way,

 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 decrease to:

 A=a(a|b)+ where N_a(A)=2*N_b(A), N_a(A) is even 

(we will be in state 1 and will be empty)

Case 2: The stack is all b.

Similarly, you can see that each cycle will look like: b * ab * a. and in each cycle exactly one "b" will be deleted. Whenever "b" is received, "b" is pushed onto the stack. Thus, when the stack is empty and we return to state 1, the number of loops accepted is equal to the number "b that we accepted / pushed onto the stack. Thus,

 B=b(b*ab*a)^n where N_b(B)=n 

But you can see n = N_a (B) / 2. In this way,

 B=b(b*ab*a)+ where N_a(B)=2*N_b(B) 

This will decrease 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 loop can be taken 0 or 1 times,

In this way,

 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 decrease to:

 S=((a|b)+)* where N_a(S)=2*N_b(S) 

which will decrease to:

 S=(a|b)* where N_a(S)=2*N_b(S) 

QED