[Solved] P4 CS373

Construct a PDA that accepts { x#y | x, y in {0, 1}* such that x y and x_i = y_i 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 (x_i = y_i for some i) and a symbol that does not match at the same index of x and y (x_j y_j for some j). One way that this can be accomplished is by finding an index i such that x_i = y_i and x_i+1 y_i+1 or x_i+1 = y_i+1 and x_i y_i. As in programming assignment 3, you can store the index in the stack and the values of x_i and x_i+1 in the state.

For the case where we assume that |x| |y|, you need to find an index i where x_i = y_i. Since the lengths are different, we get that x y without finding an index j in which x_j y_j. For this case, you can simple check that x₁ = y₁ and verify that |x| |y|. If x₁ y₁, 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.

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.

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 _p4.jff or _p4.jflap) and e-mail subject (CS 373 program 4). As with programming assignment 3, you can use JFLAP version 8 if you want to.