Problem 3. PDAs

In class, we defined E-DFA, E-NFA, E-RE, and E-CFG and proved they are all decidable.

(a) Formulate a definition for E-PDA that is consistent with the definitions of these languages, and prove that E-PDA is decidable. Write out all details of the proof. Hint: use the same strategy as we used for E-NFA

(b) A PDA state is said to be USELESS if the PDA never enters this state for any input string. Consider the problem of deciding if a given PDA has any useless states. Formulate it as a language, and then show that this language is decidable Hint: use a reduction, and make use of part (a)

(c) Let Sigma = {0, 1}. Consider the problem of determining whether a PDA accepts some string that contains substring 101 is decidable. Formulate it as a language, and then show that this language is decidable