I'm studying automata and I have this problem related to PDAs
construct a PDA for the language L = { w = x1y1x2y2….xnyn | where w belongs to {0,1}*, and the string y1y2….yn is the same as x1x2….xn except the 1’s in y come after the 0’s} For example the string 100111 belongs to L since x=101 and y=011. So do the strings 0011, 00, 1111, 100001, etc. However, the strings 0110, 11111001, 1100, 01, 10 do not belong to L. For simplicity, in the construction of the PDA assume the input consists of pairs of symbols in which the first belongs to x and the second to y. Thus the input alphabet is Σ = {00, 01, 10, 11}.
I realize I have to push/pop from the stack in a way that guarantees that the same input in x appears in y where 0's come before 1's a but the problem is how to check that the 0's in y come before the 1's . a hint for the solution is really appreciated
Hint 1: Since the string is the in the form xyxyxy..., you will always encounter a 1 in the x part before a 1 in the y part, even if the x and y parts are the same.
Hint 2: You're matching 1s in the x part to the 1s in the y part. Push for 1s in x, pop for 1s in y.
Hint 3: Once you pop, you can't stop. (I.e., hint #2 is not enough on its own, consider a string like 100100.)