Simulic
English

Finite state machines – traffic lights, DFAs, NFAs and regular languages

Computer ScienceAlgorithms & Problem SolvingAges 15–16

Loading…

Use with my class ✨ Customize with AI Report a problem

Step preset state machines (traffic light, vending machine, turnstile) through a sequence of events and watch the current state, the output and a trace table; add, drag and connect states to draw your own machine. An Acceptor mode tests which words a DFA or NFA accepts (binary numbers divisible by 3, words ending in ab), with the state-transition table, an equivalent regular expression and regular grammar, and NFA-to-DFA conversion. A note compares each model with the real system to discuss abstraction.

Lesson: Finite state machines: states, transitions and outputs; deterministic and non-deterministic finite automata; regular expressions and regular grammars

What it shows

A finite state machine has a finite set of states, a start state, an input alphabet and transitions of the form state + symbol → next state. It remembers nothing except its current state. A Mealy machine produces outputs on its transitions, a Moore machine attaches outputs to its states, and an acceptor answers yes or no: does a word belong to a language? The languages that finite automata accept are exactly the regular languages, which regular expressions and regular grammars also describe. Every NFA can be turned into an equivalent DFA by the subset construction.

How to use

In Machine with output mode, pick a Sample machine and click Step or Play to feed the symbols on the tape one at a time; the symbol buttons send extra events. In Acceptor mode, choose a Sample automaton, type a Word to read and step through it, then use Test or List accepted words. Open Edit machine to add, drag and connect states, or click Convert NFA to DFA.

Parameters you can change

  • Mode Machine with output, Acceptor
  • Sample machine (Machine with output mode) Traffic light, Vending machine, Turnstile
  • Sample automaton (Acceptor mode) DFA: binary numbers divisible by 3, NFA: words ending in ab, DFA: words ending in ab, DFA: even number of 1s (parity bit)
  • Word to read (empty = sample word)
  • Run speed 0.5–4 symbols/s
  • Open the Edit machine panel

Questions to explore

  1. Which details of a real traffic light are left out of the model, and why is that acceptable?
  2. Is the word 110 accepted by the divisible-by-3 automaton? Trace it state by state.
  3. Why does the NFA for words ending in ab need fewer transitions than the equivalent DFA?

Related simulations