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.

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|improve this question
1  
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
add comment

2 Answers 2

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|improve this answer
    
+1. Nice, especially for a succinct representation of case (1). –  Rick Decker Oct 4 '12 at 0:46
add comment

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|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
add comment

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.