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.


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$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, but the only thing I cannot realize that is the p+p!. Could you explain more about that? $\endgroup$ – javadr Jun 5 '18 at 22:45
  • $\begingroup$ @javadr $p!$ is a multiple of all possible $|vx|$, so to make $1^{k+(n-1)|vx|}$ cover all $1^m$ for large $m$, it is natural to let $k$ range from $p$ to $p+p!$. $\endgroup$ – xskxzr Jun 6 '18 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.