Construct a PDA that accepts { x#y#z | x, y, z in {0, 1}+ with x ≈ y, or x ≈ z, or y ≈ z }.
Define x ≈ y as follows: Let x = x1x2 … xn and y = y1y2 … ym, and let n' and m' be the largest odd values less than or equal to n and m respectively. Let x' = x1x3 … xn' and y' = y1y3 … ym'. Then x ≈ y if x' ≠ y' (that is, x1x3 … xn' ≠ y1y3 … ym').
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 two #s, and x, y, and z will be strings over {0, 1} of length greater than 0.
My PDA accepts x#y#z under any of the following conditions: |x'| ≠ |y'| or |x'| ≠ |z'| or |y'| ≠ |z'| or there exists odd value i with xi ≠ yi or xi ≠ zi or yi ≠ zi.
You should use the solution for problem 2.22 as the basis for the solution to this problem (we went over problem 2.22 in class on 2/20/2020). Problem 2.22 is to show that { x#y | x, y in {0, 1}* with x ≠ y } is context free. 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 200 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 simplistic PDA has 21 states, and my more complicated version has 15 states, and both are able to process the test strings with the default amount of memory allocated by the Java runtime machine (64MB).
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.
