Write a Java program that takes as input a PDA M and an input string w, simulates M on w, and outputs ACCEPT if M accepts w, and REJECT if M does not accept w. You will assume that the tape alphabet is ? = {0, 1} (use -1 to represent ?), the tape alphabet is ? = {0, 1, $} (use -1 to represent ?) and that the PDA has at most 20 states. The states are labeled 1, 2, . . . , 20. Suppose that the starting state is 1. In order to input the PDA you will do the following:

You will ask the user to enter the transition function ?. The user will enter a list of 5-tuples, where a 5-tuple has the form (old-state, tape-symbol, old-stack symbol, new-state, new-stack).

Next, you will ask the user to enter the set F of accepting states.

Next you will ask the user to enter the input string w. Test your program with the PDA from Example 2.14 (see also Figure 2.15), page 114-115 (run that PDA on 3 strings that are accepted and 3 strings that are not accepted).

Turn in:

The code of your program (should be well documented)

A short description of your program (1 page should be enough), including a presentation of the data structures that you have used to represent the PDA and the input string w (probably some types of arrays or linked lists).