Consider the languages below. (a) For each, regular? context free? (Y/N)

REG ? CF?

___ ___ L₁ = {0ⁿ 1^m 0^m 1ⁿ | n,m >= 0}

___ ___ L₂ = {0ⁿ 0^m 1^m 1ⁿ | n,m >= 0}

___ ___ L₃ = {0ⁿ 1^m+n 0^m | n,m >= 0}

___ ___ L₄ = {aⁿ b^m | n+m is even, n,m>0}

___ ___ L₅ = {w in (aUb)* | n_a(w) < n_b(w) }

___ ___ L₆ = {w in (aUb)* | n_a(w) < n_b(w) , n_b(w)<100 }

(b) Choose ONE non-context free language and prove that it is not context free

Note: n_a(w) means number of as in w so n_a(w) < n_b(w) means strings with fewer as than bs