I second the recommendation for "Automata Theory", the explanations are crystal clear and I learned a lot.
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.