Is the language {0^n 1^n 0^k | k != n} context free?

Question

I believe this language isn't context free, because there is no chance that a PDA could compare 2 blocks of 0's and 1's of the same length and also remember it's length for later use.

Unfortunately, I have no idea how to prove it.

I tried using the pumping lemma to no avail...

I've also tried to assume by contradiction that the language is context free and use the fact that the intersection of a context free language with a regular language is also context free (by finding some mysterious regular language L), and surprisingly (or not) - all my efforts were in vain...

Any help would be appreciated

score 4 · Accepted Answer · edited May 23 '17 at 10:24

4

Is the language { 0ⁿ1ⁿ0^k | k != n} context free?

No, the language L = { 0ⁿ1ⁿ0^k | k!=n } is not a context free language. Also, Class of Regular Languages is subset of class Context free languages.

You Idea using PDA is correct and obvious way to show that language is not context free. And we can't draw PDA for language 0ⁿ1ⁿ0^k because after matching prefix 0ⁿ to 1ⁿ stack become empty, then we don't have stored information to check weather suffix 0^K are equal to n or not.

HINT: For formal proofs

First

L = {0ⁿ1ⁿ0^k | k!=n } now complement of L is L^'.

L^' = {{0ⁿ1ⁿ0ⁿ} that is well known context sensitive language (can be proof).

And the complement of a context-sensitive language is itself context-sensitive.

Second

For Pumping Lemma:

L = {0ⁿ1ⁿ0^k | k!=n } is Union of L₁ and L₂, Where
L₁ = {0ⁿ1ⁿ0^k | k > n } and L₂ = {0ⁿ1ⁿ0^k | k < n },

L = L₁ U L₂

L₁ and L₂ both are non-context-free Language. and union of two non-context free languages are non-context-free.( that can easily proof by grammar)

Also, The union, concatenation of two context-sensitive languages is context-sensitive.

edited May 23 '17 at 10:24

Community

1
1

answered Dec 23 '12 at 14:29

Grijesh Chauhan

57,103
20
141
208

Thanks for your answer Grijesh. But I need a more formal proof (it's for a homework question). Do you guys (and girls) have any idea how to prove it ? – Robert777 Dec 23 '12 at 14:53
@Robert777 yes formal proof is possible. – Grijesh Chauhan Dec 23 '12 at 14:59
Yes, I would love to see how to solve it with the pumping lemma ! – Robert777 Dec 23 '12 at 15:37
@Robert777 I updated my answer with useful HINTS. Now Try and let me know if its still difficult. – Grijesh Chauhan Dec 24 '12 at 04:53
@Robert777 Welcome Robert! :) – Grijesh Chauhan Dec 24 '12 at 16:04

Is the language {0^n 1^n 0^k | k != n} context free?

1 Answers1

Is the language { 0n1n0k | k != n} context free?

Is the language { 0ⁿ1ⁿ0^k | k != n} context free?