Teaching Deterministic Finite State Machines

Note: All links below will open in a separate tab or window.

I commonly teach the undergraduate Programming Languages course at my institution, which includes, among other topics, coverage of finite state automata, regular expressions, push down automata, grammars, and related language concepts¹. This is the first of several planned posts where I hope to share materials that I use to teach those concepts.

At my institution, the Programming Languages course is a 200-level course, with prerequisites of a year of programming (covering through linear data structures) and a semester of discrete mathematics.

As much as possible I try to teach in a flipped classroom style², with students doing preparation work before class and then us (the students in peer groups, facilitated by me) working together to solve increasingly complex problems relating to the content.

Use Then Build

For teaching of these language concepts, I usually follow a use then build flow. For teaching deterministic finite state machines, that flow is as follows:

• Use
  • Identify the relationship between an alphabet and words composed of symbols from that alphabet
  • Identify state-based properties of deterministic finite state machines
    • Count the number of states
    • Identify the start state and the accepting state set
    • Identify the alphabet in use (as can be observed from the machine)
    • Identify transitions between states
    • Identify transitions not drawn that lead to a trash state
    • Determine whether a machine is a deterministic finite state machine
  • Trace a word through a deterministic finite state machine
    • Record the states visited
    • Indicate whether the word is accepted
  • Interpret a finite state machine
    • Describe the properties of the words in the language the machine accepts
    • Describe the size of the language the machine accepts
  • Identify and remove trash states (states not on a path to an accepting state)
• Build
  • Identify the design elements being used in a deterministic finite state machine: linear ordering, branching, looping
  • Design and test a deterministic finite state machine to accept a specified language

Videos

Over time, I have developed relatively short (5-10 minute) videos around some of these concepts that I ask students to watch as part of their preparation work³.

• Use
  • Describing the components that define a finite state machine (Length: 5 minutes, 0 seconds)
  • Tracing a word in a finite state machine (Length: 7 minutes, 18 seconds)
• Build
  • FSM design elements (Length: 8 minutes, 11 seconds)

Problem Sets

I typically have students work through four sets of problems:

• Preparation: To be done while doing the preparation reading and video watching
• Warmup: To be looked at before class, completed during class
• Advanced: Additional new problems completed during class
• Assess Yourself: Problems to be done after class as a means of gauging understanding

In most semesters, I have students complete the Preparation and Assess Yourself problems through our Learning Management System so I can have a sense of their understanding before and after content has been covered.

This PDF contains the set of problems that go along with the deterministic finite state machine material. Note that answers are not included to facilitate their reuse.

I want to acknowledge the FSM simulator website designed by Ivan Zuzak which I ask students to use for tracing and design problems (specifically, navigate to the Input automaton tab).

Footnotes

1. We spend more time on this material in our programming languages course relative to many other institutions. I realize this is a point of debate among what should be taught in such a course.

2. I have found Robert Talbert’s Flipped Learning book to be particularly instructive.

3. The preparation work also includes doing reading of associated material. The video content is generic enough that it should work alongside any relevant textbook. The videos are not comprehensive for the material covered; instead, they are additive to the reading.