Construct a PDA that accepts { a#b | a, b in {x, y}* Program 4 Solved

Description

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

For the case where we assume that |a| ≠ |b|, you need to find an index i where a_i = b_i. Since the lengths are different, we get that a ≠ b without finding an index j in which a_j ≠ b_j. For this case, you can simply check that a₁ = b_1. If a₁ ≠ b₁, 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.