Is the language { 0n1n0k | k != n} context free?
No, the language L = { 0n1n0k | 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 0n1n0k because after matching prefix 0n to 1n stack become empty, then we don't have stored information to check weather suffix 0K are equal to n
or not.
HINT: For formal proofs
- First
L = {0n1n0k | k!=n } now complement of L is L'.
L' = {{0n1n0n} 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 = {0n1n0k | k!=n } is Union of L1 and L2, Where
L1 = {0n1n0k | k > n } and L2 = {0n1n0k | k < n },L = L1 U L2
L1 and L2 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.