In JFLAP, the PDA will need to be able to handle input strings of length up to about 80 symbols using at most 4GB of memory.

Construct a PDA that accepts {a=ba,b in {x,y} such that a=b and ai=bi for some i,1imin(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(ai=bi for some i) and a symbol that does not match at the same index of a and b(aj=bj for some j). One way that this can be accomplished is by finding an index i such that ai=bi and ai+1=bi+1 or ai+1=bi+1 and ai=bi. As in programming assignment 3 , you can store the index in the stack and the values of ai and ai+1 in the state. For the case where we assume that a=b, you need to find an index i where ai=bi. Since the lengths are different, we get that a=b without finding an index j in which aj=bj. For this case, you can simply check that a1=b1. If a1=b1, then the other portion of the code (where we assume that a=b ) will accept the string