Wed 11 Sept: Conversions

  1. Assign 3 due Wednesday 9/18.
  2. Review Assign 2
  3. Kleene's theorem revisited.
  4. Building NFA from RE with recursion
  5. The idea behind building RE from FA

Fri 13 Sept: More Conversions

  1. Review of Test 1
  2. Conversion from NFA to DFA: Subset construction
  3. Example
  4. Practice 6

Mon 16 Sept: Algorithms for Regular Languages

  1. Closure properties: If language R is regular, then so is ...
  2. Product construction
  3. Practice 7
  4. Algorithms to answer questions about a regular language

Wed 18 Sept: Not Regular

  1. Assign 4 due Wednesday 9/25
  2. An example of language that is not regular: 0^n1^n
  3. Distinguishable vs indistinguishable strings. Ideas here
  4. Practice 8

Fri 20 Sept: Distinguishable Strings and Intro to CFGs

  1. Review distinguishable versus indistinguishable
  2. Practice 9
  3. A first peek at Grammars
  4. Quiz 2

Mon 23 Sept: Context-free Grammars

  1. Review Asg 3 and Quiz 2
  2. Grammars. Review intro and more grammars

Wed 25 Sept: Context-free Grammars

  1. More on Grammars. Examples: (A) Contains 101 (B) Balanced brackets (C) One letter away from a palindrome
  2. Practice 11
  3. Test on Friday: (a) Questions on Theory of Regular Languagses (Subset construction, closure/conversion properties, distinguistable/Indistinguishable strings) (b) Questions on Context-Free Grammars (CFG to English, English to CFG)

Fri 27 Sept: TEST 2