[Solved] P3 CS373

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 = x₁x₂ x_n and y = y₁y₂ y_m, and let n and m be the largest odd values less than or equal to n and m respectively. Let x = x₁x₃ x_n and y = y₁y₃ y_m. Then x y if x y (that is, x₁x₃ x_n y₁y₃ y_m).

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 x_i y_i or x_i z_i or y_i z_i.

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.

For this programming assignment, and the remainder of them for the semester, you need to follow my submission directions filename (lower case last name followed by _p3.jff) and e-mail subject (CS 373 program 3).

You may use JFLAP version 8 if you have problems with epsilon transitions with version 7.1.3