3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, but the only thing I cannot realize that is the p+p!. Could you explain more about that? $\endgroup$
    – javadr
    Jun 5, 2018 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, 2018 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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