Hacker News new | ask | show | jobs
by liyanage 2026 days ago
I second the recommendation for "Automata Theory", the explanations are crystal clear and I learned a lot.
1 comments

I found the first part, on regular expressions really excellent (though the accelerated pace made it difficult to fully grasp all the proofs). He's a still-enthused expert.

However, he didn't seem as passionate on the second part, decision languages. It's also a lot harder, yet is squeezed into even less time.

To help you assess my observation: I scored in the highest segment (IIRC 95%)... After taking the course, I would say I understand the regular expressions material fully, but not decision languages. I'm still confused about showing what complexity class something is in. e.g. the complexity class of determinng two polynomials are equivalent (PIT), like x(1 + y) + y and x + (x + 1)y.

Your experience aligns with how most people feel about learning about Decision Languages, based on my experience in that class in college.