Construct a PDA that accepts { a#b | a, b in {x, y}* such that a ≠ b and ai = bi for some i, 1 ≤ i ≤ min(|a|, |b|) }.
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 a and b will be strings over {x, y}. My PDA has 31 states and and is broken into two major sections, one for |a| = |b| and one for |a| ≠ |b|.
For the case where we assume that |a| = |b|, you need to find a symbol that matches at the same index of a and b (ai = bi for some i) and a symbol that does not match at the same index of a and b (aj ≠ bj for some j). One way that this can be accomplished is by finding an index i such that ai = bi and ai+1 ≠ bi+1 or ai+1 = bi+1 and ai ≠ bi. As in programming assignment 3, you can store the index in the stack and the values of ai and ai+1 in the state.
For the case where we assume that |a| ≠ |b|, you need to find an index i where ai = bi. Since the lengths are different, we get that a ≠ b without finding an index j in which aj ≠ bj. For this case, you can simply check that a1 = b1. If a1 ≠ b1, then the other portion of the code (where we assume that |a| = |b|) 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 4GB of memory. My PDA can handle all the test strings with the default 64MB of memory that is allocated to the heap.
You should be able to use the concepts learned for programming assignment 3 to assist you in constructing this PDA.
If you are having memory issues, try starting JFLAP from the command line allocating more memory. As an example, from the directory that JFLAP is in, enter "java -Xmx500m -classpath JFLAP.jar JFLAP". The -Xmx500m tells java to allocate 500MB of memory to the heap. By default, java only allocates 64MB to the heap.
