2 ms·
> Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible res
by JadeNB 2y ago
> Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible result.
It would be literally incredible, because the pumping lemma shows that it's false.
- jraph 2y ago> because the pumping lemma shows that it's false Ah yes, I even used to teach this actually. Sorry for the understatement xD.
- JadeNB 2y ago> Ah yes, I even used to teach this actually. Sorry for the understatement xD. No worries! Mainly I was just pleased with myself for remembering the pumping lemma, and kind of wished that I knew how to contact my professor (from back in the mid-1990s, when an intro CS course was taught out of Sipser and involved almost no actual programming) and tell him that he did such a good job that it stuck with me some 30 years later!