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

Programming nondeterministic pushdown automata

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 lecture, students first learn about pushdown automata. Then the instructor uses JFLAP http://www.jflap.org and builds a pushdown automaton with input from the class for a^nb^n. Next the students build a pushdown automaton for the language a^nb^mc^(n+m). The instructor can build one of the student's answers on the overhead with JFLAP to discuss with the class. You can talk about how it is possibly different than other solutions. This problem is similar to the previous problem. Next ask the students to build a PDA for ww^R (even length palindrome). This problem is quite a bit different than the previous two problems as this one can only be written nondeterministically. Most students will want to find the middle first. But that won't work. They need to find the middle nondeterministically. You may need to give them some hints for them to figure this one out. Again, once they figure it out the instructor can build it in JFLAP and run it on input to show how the nondeterminism works.