CSE 3502, Fall 2017
Homework 8

due 11/15/17 in class

Problem 1. Enumerators

We know that a language is recognizable if itís enumerable, and itís decidable if itís enumerable in order.

Prove that every infinite recognizable language LR, has a subset which is an infinite decidable language LD.

Hint: can you tweak the enumerator for LR so it enumerates LD?

 

Problem 2. Closure properties of TM-decidable languages

 

(a)   Show that decidable languages are closed under star. Meaning, prove that if L is decidable, then so is L*

 

(b) Show that recognizable languages are closed under concatenation. Meaning, prove that if L1 and L2 are recognizable, then so is L1 O L2

 

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
Hint: study the bookís solution for problem 4.14