Module #3: Automata

DFA's and NFA's

Objectives

1. Use directed graphs to create automata
   
2. Define deterministic finite automata
   
3. Define non-deterministic finite automata
   
4. Use automata to process strings
   
5. Create automata with specific properties
   
6. Apply automata theory to text searching
   
7. Use automata with ε-transitions
   
8. Convert non-deterministic automata to deterministic automata

Topics

1. Closure Properties of Regular Sets
   
2. Product Construction
   
3. Nondeterminism
   
4. Nondeterministic Finite Automata
   
5. Subset Construction
   
6. epsilon-transitions
   

   Applications and Importance

   1. Non-deterministic Finite Automata
   
   1. Circuits
      
   2. Expert Systems
      
   3. Maze Paths
      
   4. More
      
   2. Regular Expressions
   
   1. Tokens in programming languages
      
   2. Text Recognition
      
   3. Phone numbers
   4. String Matching
      
   
   

   Background Material

   0. Texts

   Hopcroft, Motwani and Ullman: Chapter 2
   Kozen: Lectures 4 - 6
   Sudkamp: Sections 2.3 and 2.4 and Chapter 5.

   1. Grahne Slides: Pages 16-52 Audio for these slides
   2. Wikepedia: NFA's
   3. Busch, Shiri & Grahne: Deterministic Finite Automata
   4. Busch, Shiri & Grahne: NonDeterministic Finite Automata
   5. Busch, Shiri & Grahne: More NonDeterministic Finite Automata
   6. Streaming video of Intro to Finite Automata [vPOD] 7. Streaming video of Nondeterministic Finite Automata [vPOD]

   Old Homeworks

   Homework Summer 2006 [PDF]
   Homework Solutions Summer 2006 [DOC] [PDF]

   Homework

   Homework 2 [pdf]

   Homework 2 Solutions [pdf]

   Use this tool to check your answers