When possible, use Rice's Theorems, Griebach's Theorem, and the Post Correspondence Problem rather than direct reductions. L contains at least two strings. L is infinite.
L is context-free.
But our previous construction was not effective in that it did not give us an algorithm to calculate the new set of final states. A CFG is linear if no right side of a production has more than one instance of a variable. Remember that regular grammars are right-linear, and thus linear. Show that PCP is decidable for words over a one-symbol alphabet.