§ Why loss of information is terrifying: Checking that a context-free language is regular is undecidable
This comes from applying Greibach's theorem .
I find myself thinking about this theorem once in a while, and its repercussions.
If we once had access to God who tabulated for all all regular languages
described as context free grammars, and we lost this tablet, we're screwed.
There's no way to recover this information decidably.
It shows that moving to higher models of computation (From regular to context free)
can sometimes be irreversably damaging.