Question

$Let{L}_1=$ {$0^{n+m}{1}^n{0}^m|n,m\ge 0$},
$L_2=$ {$0^{n+m}{1}^{n+m}{0}^m|n,m\ge 0$}, and
$L_3=$ {$0^{n+m}{1}^{n+m}{0}^{n+m}|n,m\ge 0$}.
Which of these languages are NOT context-free?

Answer 1

$L_1$ ={$0^{n+m}{1}^n{0}^m|n,m\ge 0$} is context free (first n+m 0's are pushed into the stack, then for each of the 1s and 0s following, we will pop the 0's in the stack one by until at the end of the word if the stack is empty then the word is accepted).
$L_2$ ={$0^{n+m}{1}^{n+m}{0}^m|n,m\ge 0$} is not context free, since two comparisons have to be made here to determine if $w\in$ $L_2$.
1.0's and 1's are equal.
2.Since m < (n+m). we have to ensure that, 0's which come after $0^{n+m}{1}^{n+m}$, are less in number, compared to n+m.
$L_3=$ {$0^{n+m}{1}^{n+m}{0}^{n+m}|n,m\ge 0$} is clearly context sensitive since have also 2 comparisons have to be made. Infact this language is same as
$L_3$={$0^x{1}^x{0}^x|x\ge 0$, which is context sensitive.