Construct a PDA that accepts { x#y#z#w | x, y, z, w in {0, 1}+ with x ≠ w and y ≠ z }.
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 three #s, and x, y, z, and w will be strings over {0, 1} of length greater than 0. My PDA accepts x#y#z#w under any of the following conditions: |x| ≠ |w| and |y| ≠ |z|; |x| ≠ |w| and y ≠ z; x ≠ w and |y| ≠ |z|; or x ≠ w and y ≠ z.
We recently went over problem 2.22 in class, and constructed a PDA that recognized { x#y | x, y in {0, 1}* with x ≠ y }. Based on the solution to problem 2.22, constructing the PDA for this programming assignment should be relatively straight forward.
Your PDA will need to be able to handle input strings of length up to about 170 symbols using at most 1GB of memory (the memory should not be an issue, but you want to stay away from using the transition ε, ε → ε in too many places).
My simple PDA, implements the four paths described above with each having its own accept state, has 46 states and is able to process the 16 test strings with the default amount of memory allocated by the Java runtime machine (64MB). My more complex PDA has 20 states, has two accepts states and uses the stack more effectively.
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 -jar JFLAP7.1.jar". The -Xmx500m tells java to allocate 500MB of memory to the heap. By default, java only allocates 64MB to the heap.
Use JFLAP 7.1 for the programming assignment.
