Historically, it has been challenging for students to get interested in and for instructors to teach Formal Languages and Automata Theory courses. The challenges stem from a multitude of reasons including the theoretical nature of the material, the use of formal notation, student lack of experience with problem solving and proof development, and the student perception that the material is not relevant to majoring in Computer Science. In this article, we illustrate our novel design- and programming-based approach to building state machines and developing constructive proofs. Student perceptions, both overall and by gender, are explored to determine if this approach effectively addresses some of the negative historical trends. Our empirical results suggest that the approach has a positive impact overall and by gender. In addition, the results reveal nuanced differences between female and male students and areas for future improvements.