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.
Is the language $L = \{0^m1^n: m \neq n - 1 \}$ context free?
-
1Try making a PDA for it. – 2011-08-11
-
0It'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?" – 2012-06-08
-
0@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. – 2013-02-09
-
0@AsafKaragila, sorry about that. Really didn't look at the dates. – 2013-02-09
3 Answers
we have 3 basic ways to check if a grammar is CFL,
- draw a PDA
- pumping lemma
- get a stack, and check if by 2 operations(push/pop) u can achieve the target
I will go with the stack method here,
we need 0 or more 0s followed by 0 or more 1s, given that no of 0s should not be 1 less than the no of 1s.
Sol:-
try pushing as many 0s as you get.
once you receive 1, start popping the 0s(if any)
at the end of the input,
if there exists a single 0 in the stack, reject the string else, accept the string.
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.
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.
-
0Thanks 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. – 2011-08-11
-
0For 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". – 2011-08-11
-
0Sorry for the late reply, I finally figured it out. Thank you. – 2011-08-21