I taught the theory of computation for the first time in Fall 2013. This course explores different types of automata (state machines). An automaton is a process defined by logical states and transitions that act as instructions changing the process from one state to another. These automata are fully automatic when given an input string. The course develops the mathematics of how computation works by analyzing the different types of automata (some with memory and some without).
The first lecture of the course is about deterministic finite automata (DFAs). A DFA is a process comprising 5 components∶
| 2 | an input alphabet (for defining an input string) |
|
| 3 | a transition function (the instructions) |
|
| 4 | the initial state (where computation starts) |
|
| 5 | a set of final states (to determine the result of the process) |
|
A state machine can be visualized using a directed graph called a state diagram. The state diagram for a DFA is described as vertices (representing the states) and edges (representing the transitions). An arrow points to the initial state to show where the computation begins.
Creating state diagrams for lecture slides proved to be difficult and very time consuming for me. I do not see well and have difficulty with point-and-click interfaces. When creating slides for the first lecture on deterministic finite automata, it took me so long to draw one state diagram that it was clear that using presentation software would not be feasible.
Since I am a computational linguist and have designed programmable languages for my previous software projects, it occurred to me that I could design a programming language for defining a state machine using syntax that was close to the mathematical syntax that I used in class. Once the computer had an understanding of the automaton, I could write a program to automate the generation of a state diagram graph. I named my program Grafstate because it drew graphs of state machines.
The first feature of the Grafstate software was to draw state diagrams for DFAs. It worked by parsing the Grafstate code for a DFA (consisting of a set of states, a set of input symbols, the points of the transition function, the starting state, and the set of final states). Once the 5 components of the state machine were determined, the small compiler constructed a directed graph. The states were represented as vertices in the graph, and the points of the transition function were represented as directed edges. I used an open source rendering tool to draw the images of the graphs. I expanded this model for the other types of state machines (NFAs, GNFAs, PDAs, and Turing Machines).
The original Grafstate language for defining a DFA has evolved but was similar to the following∶
Code |
|---|
:+ dfa M
title Binary strings ending with 1
Q={q1,q2}
S={0,1}
d(q1,0)=q1
d(q1,1)=q2
d(q2,0)=q1
d(q2,1)=q2
q0=q1
F={q2}
done. |
The Grafstate code above produces the following state diagram∶
| Deterministic finite automaton |
|---|
 |
M
This procedure allowed me to create all of the state diagrams for my slides. Since I designed the Grafstate notation to be similar to the mathematical notation used in the course, I included my Grafstate code in my slides to emphasize the computability of the constructions.
During one lecture when I described the Grafstate process, multiple students in the class asked if they could use Grafstate themselves to create the state diagrams. I responded by making some modifications to make it accessible with a web browser. The original online interface was a simple form for each state machine type. A student could enter the mathematical description of an automaton in one of the forms. Submitting the form would cause Grafstate to display the image for the state diagram.
Other offline tools were available for constructing state machines by using the mouse to position states on the screen; edges could also be drawn manually between the states. I made the decision not to provide this type of interface because one of my goals in teaching is to improve and encourage math literacy among my students. I expect students to understand the math well enough to read it and write it proficiently. It was my assessment that the drag-and-drop interface did not have a direct connection between the math and the visualization of the math.
Several students commented that the ability to describe a mathematical structure using Grafstate notation and see a visualization of the corresponding state machine helped them to connect the meaning of the notation to the visual logic of the machine. The Grafstate language gave them the ability to explore their own examples by modifying examples from class or by defining completely new machines.
The next level of abstraction for the students after visualization of a state diagram was simulation. A simulation of an automaton with an input string determines all steps performed by the machine during computation and produces a visualization of those steps. The simulation of a DFA is straightforward since it produces a linear sequence, like the one below∶
Simulation |
|---|
Input 1001 |
Result ACCEPTED |
 Explanation The following computation path shows all steps of the computation∶ |
 |
Deterministic finite automaton∶ M
After we got to the automata that contained memory as a component (Pushdown automata and Turing machines), the simulations became more difficult to visualize. A student asked me one day if Grafstate would be able to show the simulation of an automaton on a string. I said that I could do that and asked if it would be helpful. The students overhearing the conversation agreed that it would have helped them. It was too late for me to implement these features for that semester, but Grafstate was able to simulate PDAs and Turing machines the next time I taught the class. The visualization of the rest of the machine types came a bit later.
Most of the features and improvements in Grafstate have come as responses to the following∶
| 2 | my observations of problems faced during the previous semester |
|
| 3 | motivation to improve my teaching in an out of the classroom |
|
Students have provided a vital source of feedback for developing Grafstate to meet the learning objectives for the course. Student feedback has taken the following forms∶
| 1 | requests for new features |
|
| 2 | feedback on interface or on the syntax |
|
| 4 | end-of-semester evaluations |
|
I try to address all comments of the above types in some way. That may involve adding a major feature or adjusting the syntax; it may involve something smaller like a bug fix or adding some more documentation.
I continue to add new accessibility features that help me with my teaching and that help students to use the Grafstate language. In addition to adding new features, I continue to update the syntax on the language to attempt to achieve the right balance of being a representation of the language of mathematics while also being accessible to the students.
Currently, Grafstate is used in all sections of the theory of computation at the University of Georgia. I am working to expand the visualization and simulation features to help with other math-based courses.