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.
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
Reviews
There are no reviews yet.