SP18:Lecture 23

From CS2800 wiki
Revision as of 09:23, 17 October 2018 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

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