Extremely rough notes for FSMs and REs

• From CourseTopics

  • intro RE languages (and formal languages generally)
  • intro FSMs
  • build mini-parser
  • pumping lemma
• Things you should know before class
  • What is an FSM? Be able to draw one, determine whether a string is accepted by one (at least a DFSM).
  • Have seen formal representation of FSM, particularly transition table
  • What is a DFSM? An NDFSM?
  • Bonus for EE/CE types: What's the difference between a Moore machine and a Mealy machine?
  • What is an RE? Be able to write one, read one.
• Things we might do in class
  • Show full formalization
  • Show some transformations/proofs, e.g. DFSM/NDFSM, Moore/Mealy
  • Show equivalence of REs and FSMs
  • Play FSM games
  • Human interest: Uses of REs and FSMs, including Brooks AFSM subsumption, RE in language tools, some really hardware-y example

    • Microsoft Web Wizards and FSMs

    • open source, too. check out demo.

    • from UML

    • design pattern eg. from Harvard Extension/David Sullivan

  • Pumping lemma and limitations of REs/FSMs

Need to work out resources for learning this stuff, specific pencil and paper exercises, specific programming exercise, specific class session content.

• Possible readings sources

  • Wikipedia on FSMs -- too short by itself, but combined with articles on DFAs, NDFAs, etc. and REs, etc., a reasonable if succinct summary. Includes, e.g., a proof of the Pumping Lemma

  • Lecture notes to vet:

    • David Eppstein UC Irvine (Algorithms!)

      • clear, though prior understanding of C and grep help. -kmr

      • "I like String matching and the following lecture notes but Katie's caveats are real -las

    • Marvin Nakayama NJIT pdf notes and psets

    • Barbara Partee UMass pdf notes and psets (Linguistics!)

    • Jon Squire U Maryland (BC) plain text (?) notes and psets, v. nice definitions/refs, etc.

      • Automata Definitions and Formal Languages from this set are probably appropriate, though requiring all of either of them might be a bit much for nontheoreticians. -kmr

    • Fritz Ruehr Willamette Automata theory with some reasonable programming projects

    • Jeremy Nimmer ESP MIT Succinct not deeply mathematical hardware-biased but hands-on notes

    • from Pitt lecture notes, not vetted, avail for indiv use only

  • Bonus on Moore/Mealy w/hardware perspective

    • Took more than one reading to understand(the diagrams threw me off), but once I did, good. -kmr

• Possible activities sources

  • http://www.cs.uwaterloo.ca/High_School_Liaison/girls/june2002/resources/fsm.pdf Very brief intro w/pointers to JFLAP

  • JFLAP is a Good Thing, but what exactly should they be asked to do with it?

    • JFLAP reminds me of NodeNet from Java-PI. What's neat is that with a minimal idea of what's going on(ie, knowing what characters are valid; knowing that + and * are not math operators) you can figure out how regexps and state diagrams relate and convert to one another, mostly by guessing and learning from experience. It's fun. I'd think a, "Play with this, make an automata that expresses this regexp, make a regexp that expresses this automata, find two automata that express the same thing but look different" sort of thing would work, but I'm not certain if that's what you're looking to get out of this widget. --Katie

  • Fritz Ruehr Willamette Automata theory with some reasonable programming projects

  • lesson plans oriented towards younger audience