How do you teach Theory of Automata / Formal Language Theory / Computation Complexity?
The course is often theoretical, taught like a math course, which it is, actually. In fact, my daughter has a doctorate in Philosophy and this was one of her doctoral courses since it relates to Epistemology. 

There is actually more material than can be covered in a single course, I think. Formal language theory could be introduced as part of a Languages and Compilers sequence to separate it out a bit. This is how I taught formal languages so as to motivate scanners and parsers. 

Automata and Computability is quite a lot on its own. 

There is a third way to teach the course, actually, which is to teach the insights, rather than going through the proofs. What does it all actually mean if you look at it from a bit of a distance. What does it mean for problems to be equivalent? 

But if you want to have a course that includes programming, you should at least look at JFlap, which is a system for teaching the course and was developed by Susan Rodger at Duke. The system lets you simulate finite automata and can support either a theoretical or insight driven course. 

There are a couple of old books, now somewhat hard to find, that I consider classics and excellent introductions. Both are by V. J. Rayward-Smith:

A First Course in Formal Language Theory

A First Course in Computability

These are both small books but are good for the basics and for generating insight. They are worth having, even if you don't use them as course texts. 

There have been a lot of books published since I studied this subject. If I had to teach a complete course, the first book I would consider would be
Introduction to the Theory of Computation by Michael Sipser. I expect it would be clear and deep.