CS 3100 -- Models of Computation -- Fall 2010

August 24, 2010

• General introduction
• ----
• Tape, tape head, memory, transitions
• ----
• JFLAP illustration
• ----
• Strings accepted, language recognized
• Examples from book
• ----
• Alphabet, language, language of an FA, unary language
• ----
• Length of a string, empty string, ``epsilon'' ()
• ----
• Representation in terms of Q, S, q₀, T (accepting states), d
• Example 1.6
• ----
• When do FA exist:
  • Balanced parantheses
  • Parity
  • mod
  • Is legal ASCII
  • Is legal 10-digit phone number
  • num 0's > num 1's
  • of the form n zeros, then n ones, then n twos
  • Is legal 10-digit phone number with a one-bit parity error somewhere
  • Scan LSB-first and value is divisible evenly by 3

This document was translated from L^AT_EX by H^EV^EA.