Concepts, definitions (in italics):

• Equivalent regular expressions
• Regular languages
• finite state automata (FSAs) - states, input characters, transitions
• 3 representations for FSAs (diagram, table, sets)
• a computation of an FSA - sequence of 0 or more transitions
• a valid computation of an FSA
• an accepting computation of an FSA
• a string w accepted by an FSA A - if there exists an accepting computation of A on w
• the language recognized (accepted) by an FSA (= set of strings accepted by FSA)

Reading:

• sec. 1.1 through fig. 1.22

• Know new definitions, understand new concepts
• Write a formal (set-based) FSA description from an FSA diagram or table
• Construct a diagram/table given a formal FSA description
• Determine whether a given string is accepted by a given FSA
• What is a computation of length 0? What does it accept?
• Determine the language recognized by a given FSA

• Definition 1.7 is an alternate definition of a regular language; we will prove that the two definitions are equivalent.
• For any regular language, there may be multiple regular expressions that specify it; simpler ones are preferable.
• The formal description of an FSA is a quintuple (Q, S, d, q₀, F)
• Note: the book's definition of d is different from the one I provided; theirs is a mapping from the pair (state, symbol) to new state, rather than a set of triples (state, symbol, new state).
• a computation of an FSA A on input string w is a sequence of transitions in A; it is valid if:
  • 1st transition starts at initial state
  • each next transition starts where previous one ended
  • the labels along this sequence of transitions "spell out" w
• A valid computation is accepting if
  • last transition ends at final state

• Example of proof. (Notation: bold font indicates regular expressions, italics indicate strings.)

  To prove: abcdad Î (a(bc)*d)*.

  Proof:

  1. Let w₁ = a; w₁ Î a (from rule 1 of definition 1.26)
  2. Let w₂ = b; w₂ Î b (from rule 1 of definition 1.26)
  3. Let w₃ = c; w₃ Î c (from rule 1 of definition 1.26)
  4. Let w₄ = w₂w₃ = bc;  w₄ Î cd (from steps 2 and 3, from definition 1.26, and from definition of concatenation)
  5. w₄ Î (bc)*  (from step 4, from definition 1.26, and from definition of star)
  6. Let w₅ = w₁w₄ = abc; w₅ Î a(bc)* (from steps 1 and 5, from definition 1.26, and from definition of concatenation)
  7. Let w₆ = d; w₆ Î d (from rule 1 of definition 1.26)
  8. Let w₇ = w₅w₆ = abcd; w₇ Î a(bc)*d (from steps 6 and 7, from definition 1.26, and from definition of concatenation)
  9. Let w₈ = e; w₈ Î (bc)*  (from definition 1.26, and from definition of star)
  10. Let w₉ = w₁w₈ = a; w₉ Î a(bc)* (from steps 1 and 9, and from definition of concatenation)
  11. Let w₁₀ = w₉w₆ = ad; w₁₀ Î a(bc)*d (from steps 10 and 7, and from definition of concatenation)
  12. Let w₁₁ = w₇w₁₀ = abcdad; w₁₁ Î (a(bc)*d)* (from steps 8 and 11, and from definition of star)

  QED