Field Reports tell how instructors have used AVs in their teaching.

Interactively experimenting with finite state machines

No replies
rodger
rodger's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-06-05
Posts:
Points: 196
Instructor(s): 
Susan Rodger
Location: 
Duke University
Course: 
CompSci 140: Mathematical Foundations
Term / Date: 
Spring 2009
AVs used: 

In this lesson, we first introduce the formal definition of a deterministic finite automaton (DFA) and then show how using JFLAP you can build one. The students then build a DFA for another language. Next we show the formal definition for a nondeterministic finite automaton (NFA) and again build an example with JFLAP for students, showing how to run it and where the nondeterminism is shown. Next the students build a particular NFA and then one of them can describe it and we build it in front of the class with JFLAP. We then compare NFA and DFA and study two algorithms, one for converting an NFA to a DFA, and a second one for converting a DFA to a minimal state DFA. We then go over both algorithms in JFLAP by creating an NFA and showing how to convert it to a DFA, and then how from there to convert it to a minimal state DFA. This lesson is for 2-3 75 minute lessons.