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.
A question on context-free languages from Sipser's computation book
-
0I don't answer textbook exercises but here is a hint: start by removing the rules containing terminal symbols other than 1. – 2012-01-30
3 Answers
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.
-
1Also, the given grammar fragment is far from unique for $\{1\}^*$, so checking for only it will not work out. – 2012-02-09
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/
Did no one really bother reading the book/this question? The problem doesn't ask for a CFG of DFA that recognizes this language but for a proof that this language is decidable, i.e. there exists a TM that always halts that determines whether some arbitrary CFG/DFA accepts all of the strings in 1*.
The proof that this language is decidable is here