SP18:Lecture 23

From CS2800 wiki

We show that there are unrecognizable languages in three ways:

  1. using Cardinality
  2. by showing [math]\{0^n1^n \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n \href{/cs2800/wiki/index.php/%5Cin}{\in} [[\mathbb{N}]]\} [/math] is unrecognizable
  3. using the pumping lemma