COSC 340: Theory of Computation

Study Guide 1

Regular Languages

Sections Covered

  • Section 1.1 (Deterministic Finite Automata)
  • Section 1.2 (Nondeterministic Finite Automata)
  • Section 1.3 (Regular Expressions)

Topics Covered

DFAs

  • What is a regular language?
  • Know how to read/create DFAs
  • What language does this DFA recognize?
  • Given a language, come up with the DFA that recognizes it.
  • Know the three regular operations (union, concatenation, star)
  • Know how to prove that the union of two regular languages is regular.

NFAs

  • Know how to read / create NFAs
    • What language does this NFA recognize?
    • Given a language, come up with the NFA that recognizes it.
  • Know the three regular operations (union, concatenation, star)
    • Know how to prove that the union of two regular languages is regular.
    • Know how to prove that the concatenation of two regular languages is regular.
    • Know how to prove that the star of a regular language is regular.
  • Know that DFAs and NFAs are equivalent in power (recognize the same languages).
    • Know how to convert an NFA to a DFA.
    • Know how to convert a DFA to an NFA (don’t overthink this!).

RegExs

  • Know how to read/create RegExs
    • What language does this RegEx generate?
    • Given a language, come up with the RegEx that generates it.
  • Know that DFAs and NFAs and RegExs are all equivalent in power.
    • Know how to convert a RegEx to an NFA.
    • Know how to convert a DFA/NFA to a RegEx.