Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I don't answer textbook exercises but here is a hint: start by removing the rules containing terminal symbols other than 1. –  Kaveh Jan 30 '12 at 6:17

2 Answers 2

up vote -3 down vote accepted

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.

share|improve this answer
    
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)? –  Ted Jan 27 '12 at 3:55
    
@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$. –  Unreasonable Sin Jan 27 '12 at 5:54
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 (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? –  Ted Jan 27 '12 at 6:18
    
@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. –  Unreasonable Sin Jan 27 '12 at 7:16
1  
Also, the given grammar fragment is far from unique for $\{1\}^*$, so checking for only it will not work out. –  Raphael Feb 9 '12 at 11:21

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/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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