Construct a PDA that accepts { x#y | x, y in {0, 1}* such that x ≠ y and xi = yi for some i, 1 ≤ i ≤ min(|x|, |y|) }.
For your PDA to work correctly it will need to be non-deterministic. You can assume that you will always be given a valid string – that is, the input will always contain one # and x and y will be strings over {0, 1}. My PDA has 31 states and and is broken into two major sections, one for |x| = |y| and one for |x| ≠ |y|.
For the case where we assume that |x| = |y|, you need to find a symbol that matches at the same index of x and y (xi = yi for some i) and a symbol that does not match at the same index of x and y (xj ≠ yj for some j). One way that this can be accomplished is by finding an index i such that xi = yi and xi+1 ≠ yi+1 or xi+1 = yi+1 and xi ≠ yi. As in programming assignment 3, you can store the index in the stack and the values of xi and xi+1 in the state.
For the case where we assume that |x| ≠ |y|, you need to find an index i where xi = yi. Since the lengths are different, we get that x ≠ y without finding an index j in which xj ≠ yj. For this case, you can simple check that x1 = y1 and verify that |x| ≠ |y|. If x1 ≠ y1, then the other portion of the code (where we assume that |x| = |y|) will accept the string.
Your PDA will need to be able to handle input strings of length up to about 80 symbols using at most 1GB of memory. My PDA can handle all the test strings with the default 64MB of memory that is allocated to the heap.
