4
$\begingroup$

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.

  • 0
    I 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 3

-5

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.

  • 0
    Is this guaranteed to work? Do we know that every CFG that accepts 1* can be transformed into the above rule by "replacing variables with terminals" (I'm not completely sure what that means)?2012-01-27
  • 0
    @Ted, if we have the rule $B \rightarrow 1$ then in any rule that contains the variable $B$ we replace it with $1$. We continue in this manner until we reach the start variable $S$.2012-01-27
  • 4
    @Unreasonable Sin I don't quite understand, maybe you can explain how it would work on the following family of grammars (or just a specific member of the family). Fix positive integers $m$, $n$. Consider the grammar $S \to T\,|\,\epsilon | 1 | 1^2 | \ldots | 1^{mn - m -n}$, $T \to \epsilon\,|\,TT\,| 1^m | 1^n$. This grammar generates $1^*$ iff $m$ and $n$ are relatively prime (http://en.wikipedia.org/wiki/Coin_problem#n_.3D_2). How does your procedure work when $m$ and $n$ are relatively prime, and where does it fail when they are not?2012-01-27
  • 0
    @Ted Ahhhh you're right! This is problem 4.14 from Sipser's text and it's pretty difficult. I'll have to think some more about it.2012-01-27
  • 1
    Also, the given grammar fragment is far from unique for $\{1\}^*$, so checking for only it will not work out.2012-02-09
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/

1

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