Using Computation Graphs to Explain Nondeterminism to Students
summary
Paper introduces computation graphs implemented in FSM (a Racket DSL) that visualize nondeterministic runs by highlighting states in the original transition diagram rather than showing configuration trees. Tool shows dynamic traces only for accepted words, creates a dead state and dashed edges for unconsumed input, and uses a cutoff threshold (gold highlight) to handle likely infinite computations. Classroom study with 17 students reports over 80% top scores for usefulness, and the graphs help pinpoint whether rejection is due to halting in nonfinal states or missing transitions.
AI-written summary · about
chapters (11)
- 0:00Computation graphs for nondeterminism
- 1:25Nondeterminism in FSM challenges
- 2:50Trees vs computation graphs
- 5:17Why graphs help students
- 7:25Implementing FSM machines
- 9:13Graphs for accepted words
- 10:57Visualizing accepted words
- 12:00Rejected words analysis
- 14:09Student study on graphs
- 15:55Conclusion and future work
- 16:37Q&A