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.

Consider the language: $L = \{0^m1^n : m \neq n - 1 \}$ where $m, n \geq 0$
I tried for hours and hours but couldn't find its context free grammar. I was stuck with a rule which can check on the condition $m \neq n - 1$. Would anyone can help me out? Thanks in advance.

share|improve this question
1  
Try making a PDA for it. –  Unreasonable Sin Aug 11 '11 at 3:15
    
It's a bit late now, but in your title, a language is a set of strings. That's not the same thing as a grammar. A better choice would be "Is the language (...) context-free?" –  Rick Decker Jun 8 '12 at 18:04
    
@vonbrand: It's one thing to fix small errors in new posts (i.e. posts from the past day or two), but it's another to bump something from two and a half years ago just to remove one word from the title. –  Asaf Karagila Feb 9 '13 at 2:36
    
@AsafKaragila, sorry about that. Really didn't look at the dates. –  vonbrand Feb 9 '13 at 2:39

2 Answers 2

up vote 2 down vote accepted

The trick is that you need extra "clock" letters $a,b, \dots$ in the language with non-reversible transformations between them, to define the different phases of the algorithm that builds the string. When the first phase is done, transform $a \to b$, then $b \to c$ after phase 2, etc, then finally remove the extra letters to leave a 0-1 string. The natural place for these extra markers is between the 0's and the 1's, or before the 0's, or after the 1's.

The string can be built by first deciding whether $m - (n-1)$ will be positive or negative, then building a chain of 0's (resp. 1's) of some length, then inserting 01's in the "middle" of the string several times. Each of these steps can be encoded by production rules using extra letters in addition to 0 and 1.

share|improve this answer
    
Thanks a lot for your hint. Would you mind giving me a similar example to this problem? since the book I'm reading has very few examples and it's hard to practice the theorem. I still can't picture it in my mind. –  Chan Aug 11 '11 at 4:47
    
For example, how to generate the language 0^n 1^n (strings with a block of 0's followed by a block of 1's of the same length). Next, how to generate the language whose strings are "BLUE 0^n 1^n GREEN". –  zyx Aug 11 '11 at 9:22
    
Sorry for the late reply, I finally figured it out. Thank you. –  Chan Aug 21 '11 at 21:28

Write grammars for languages $\{0^m 1^n \colon m < n-1\}$ and $\{0^m 1^n \colon m > n-1\}$ and create their sum. As a simplification, you can try to write grammar for $\{0^m 1^n \colon m \leq n\}$ first.

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.