1
$\begingroup$

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?

  • 1
    You could also construct a pushdown automaton that accepts all and only the strings in the language.2012-10-03

2 Answers 2

3

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; 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$.

  • 0
    +1. Nice, especially for a succinct representation of case (1).2012-10-04
0

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$

  • 0
    It doesn't. Your CFG does not accept, for example, 0101, which is a member of the language requested.2012-10-03