0

I have a question..Using the closure properties,I have to show that the language $\left \{ w\epsilon \left \{ 0,1 \right \}^{*}:w\neq 0^{m}1^{m},m\geq 0 \right \}$ is contextfree.Could you give me a hint how to start?

evinda
  • 7,823

1 Answers1

2

In order to show this using closure properties one has to start with at least one language known to be context-free. Here $K = \{ 0^n1^n \mid n\ge 0\}$ is a good choice.

You want to show that the complement of $K$ also is context-free, but alas context-free languages are not closed under complement. We can however write your language as the usion of (1) strings $0^m1^n$ with $n>m$ (2) idem with $n<m$ (3) strings not of the form $0^*1^*$.

Language (3) is regular, languages (1) and (2) can be obtained from $K$ using simple language operations.

Hendrik Jan
  • 1,910
  • Is it maybe $(1)\cap (2)=K$ ?or not? – evinda Dec 29 '13 at 00:05
  • 1
    No $(1)\cap(2)=\varnothing$, but that is not the point. – Hendrik Jan Dec 29 '13 at 00:50
  • What language operations do you mean that I have to use for (1) and (2) ? – evinda Dec 31 '13 at 01:33
  • 1
    Assuming $m>n$ then $0^m1^n = 0^{m-n}\cdot 0^n1^n$. – Hendrik Jan Jan 01 '14 at 20:35
  • So,is (2) the union of the languages: ${0^{m-n}:m-n>0}$ and $K$ ? – evinda Jan 02 '14 at 01:25
  • 1
    Dear @evinda, I invite you to review the language operations. Concatenation, not union. Also ${0^m-n \mid m-n>0}$ is better written as $0^+$. – Hendrik Jan Jan 02 '14 at 09:30
  • 1
    So, $(2)=0^{+}K$ is contextfree, as contextfree languages are closed under the concatenation. Similar,$(1)=1^{+}K$ is contextfree. $(3)$ is regular. So, the language is $(1)U(2)U(3)$ . $(1)U(2)$ is contextfree,because contextfree languages are closed under the union. But,is the union of a contextfree with a regular language also contextfree? – evinda Jan 02 '14 at 23:09