A question on context-free languages from Sipser's computation book

Question

I'm trying to learn some computability theory, and I came across a question in Sipser's book that I can't figure out. The exercise asks to show that there is an algorithm which will accept a context-free grammar $G$ and decide whether or not $\{1\}^*$ is a subset of the language generated by $G$. I was trying do some kind of pumping while looking for patterns in the stack contents, but I couldn't get it to work. After examining stack contents, is there some kind of maximal length after which you can stop checking any longer string of 1's? Any hint would be appreciated.

Answer 1

For a problem like this it is easier to work with the CFG than the PDA. You should start at the terminal $1$ and work your way back to the start variable $S$. By replacing variables with terminals, you eventually want to show that the rule

$S \rightarrow \epsilon \; |\; 1S\; |\;S1$

exists in the CFG.

Answer 2

This interesting problem seems to have no simple solution. It is tied to the fact that unary context-free languages (i.e., over a single letter alphabet) are actually regular. This is a quite advanced application of pumping, a special case of Parik's Theorem. For regular languages the property is decidable. This should be contrasted to the two-letter case (can we generate every string in $\{0,1\}^*$) which is undecidable/