CSCI 250 (GOLDWEBER)
Spring 08: 2/10/08 Study Guide #1

Chapters 1 & 2 of the text in addition to all Web pages associated with the course.

• Introductory Material:
  • Why study "Languages and Automata?"
  • What is an Algorithm?
  • What one hopes to learn/accomplish be the end of the semester?
  • What is a Language?
• Finite Automata:
  • Deterministic FA, Non-deterministic FA with and without -transitions.
  • The equivalence between DFA and NFA and the basic structure of the proof.
• Regular Expressions:
  • What are RE's and what are they used for?
  • The recursive rules for constructing legal RE's.
  • Kleene's Theorem: The equivalence of RE's and NFA's.
  • Sorting: Selection Sort and Insertion Sort.
• Regular Languages
  • The utility of regular languages.
  • Closure properties and decision problems for regular languages.
  • The pumping lemma and showing that a language is not regular.

---

File translated from T_EX by T_TH, version 3.74.
On 10 Mar 2008, 14:57.