Finite State Machines and the NCTM Curriculum Standards
The Foundational Four
Mathematics as Problem Solving, Mathematics as Communication, Mathematics as Reasoning, and Mathematical Connections are critical items throughout the NCTM Standards. They appear at every level because they form the core of what it means to do mathematics.
Here are some of the ways that students will engage in these activities when they experiment with finite state machines:
Problem-solving and reasoning come into play when students try to find words that a machine will accept, or they try to design a machine that will only accept certain words.
These abstract drawings are communication tools that computer scientists use to describe the way that they will design machines or programs that will recognize patterns, and of course students will have to find ways to communicate with one another about them if they collaborate on problems involving finite state machines.
When you use ordinary descriptive language to try to describe what a finite state machine does, you often find your words going on endlessly and somewhat ambiguously without fully saying exactly what possibilities are covered by a simple little drawing. When this happens, students are ready to learn the descriptive power of notational tricks, and to appreciate how mathematical notation isn't something that is invented to make things confusing, it is invented to make communication among mathematicians more clear!
Finite state machines have been used primarily in the design of computer systems, but they can also describe other situations where the rules are rigid. Studying finite state machines creates a context for helping students make connections between rules and the systems that underlie them.
Patterns and relationships
Computer scientists use finite state machines to solve problems that involve pattern recognition. But a finite state machine only recognizes certain kinds of patterns. This invites discussion of what constitutes a "pattern" and how various types of patterns might be classified and recognized.