Prove $\{0,1\}^* -\{0^i 1^i\mid i \ge 0\}$ is context free?

Question

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?

You could also construct a pushdown automaton that accepts all and only the strings in the language. — Rick Decker, Oct 03 '12 at 20:28

score 3 · Accepted Answer · answered Oct 03 '12 at 20:30

3

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

any word of the form $x10y$, where $x,y\in\{0,1\}^*$;
any word of the form $0^i1^k$ with $i<k$; and
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$.

answered Oct 03 '12 at 20:30

Brian M. Scott

616,228

+1. Nice, especially for a succinct representation of case (1). – Rick Decker Oct 04 '12 at 00:46

score 0 · Answer 2 · answered Oct 03 '12 at 20:35

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

answered Oct 03 '12 at 20:35

Hagen von Eitzen

374,180

It doesn't. Your CFG does not accept, for example, 0101, which is a member of the language requested. – Paul Z Oct 03 '12 at 23:19

Prove $\{0,1\}^* -\{0^i 1^i\mid i \ge 0\}$ is context free?

2 Answers2