Decidability of determining whether a context-free grammar generates all strings in 1*

Question

How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Theory of Computation" by Michael Sipser.

Answer 1

You can find the solutions to the exercises of that book here. For completeness of the answer, I rewrite the solution (with some more details) here.

Let $p$ be an upper bound of the pumping length of $G$, you only need to check whether $1^0, 1^1,\ldots,1^{p+p!} \in G$. If not, we can certainly reject $\langle G\rangle$. Otherwise, applying pumping lemma on $1^k$ ($p\le k\le p + p!$), we can conclude that there exist substrings $u,v,w,x,y$ such that

• $1^k=uvwxy$, which means $u,v,w,x,y$ contain only 1s,
• $|vwx|\le \text{pumping length} \le p$,
• $|vx|\ge1$ and
• $uv^nwx^ny\in G$, i.e. $1^{|uwy|+n|vx|}=1^{k+(n-1)|vx|}\in G$, for all $n\ge 0$, which means $1^{k+n(p!)}\in G$ for all $n\ge0$.

Note $\{1^{k+n(p!)}\mid n\ge0, p\le k\le p + p!\}$ covers all $1^m$ for large $m$, so $1^0, 1^1,\ldots,1^{p+p!} \in G$ indeed implies $1^*\subseteq G$.