Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is the only way to prove that this language is context-free to construct a Context-Free Grammar that accepts it?

If so any hints on how to get started?

share|cite|improve this question
You could also construct a pushdown automaton that accepts all and only the strings in the language. – Rick Decker Oct 3 '12 at 20:28
up vote 3 down vote accepted

HINT: Let $L=\{0,1\}^*\setminus\{0^i1^i:i\ge 0\}$. Then $L$ consists of all words of the following three kinds:

  1. any word of the form $x10y$, where $x,y\in\{0,1\}^*$;
  2. any word of the form $0^i1^k$ with $i<k$; and
  3. any word of the form $0^i1^k$ with $i>k$.

It’s not hard to write context-free grammars for each of these types, and once you have them, it’s not hard to combine them into a single context-free grammar that generates $L$.

share|cite|improve this answer
+1. Nice, especially for a succinct representation of case (1). – Rick Decker Oct 4 '12 at 0:46

What do you think about the following? Does it work? $$S\to M1X$$ $$S\to X0M$$ $$M\to 0M1$$ $$M\to \Lambda$$ $$X\to 1X$$ $$X\to 0X$$ $$X\to \Lambda$$

share|cite|improve this answer
It doesn't. Your CFG does not accept, for example, 0101, which is a member of the language requested. – Paul Z Oct 3 '12 at 23:19

Your Answer


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.