COSC 340: Theory of Computation

Study Guide 2

Context-Free Languages

Sections Covered

  • Section 1.4 (Nonregular Languages)
  • Section 2.1 (Context-Free Grammars)
  • Section 2.2 (Pushdown Automata)

Topics Covered

Nonregular Languages

  • What is a nonregular language?
  • Know some examples of nonregular languages
  • The Pumping Lemma
    • Know what the pumping length is
    • Know what the lemma itself is, what it’s used for, and how to use it

Context-Free Grammars (CFGs)

  • How how to read/create CFGs
    • What language does this CFG generate?
    • Given a language, come up with the CFG that generates it.
    • Give 3 strings that this CFG generates
  • Know what Chomsky Normal Form (CNF) is, and how to convert any grammar into CNF form.
  • Know how to convert a DFA to a CFG
  • Know that CFGs are more powerful than DFAs, NFAs, and REGEXs (recognize the same languages, plus more).

Pushdown Automata (PDAs)

  • Know how to read/create PDAs
    • What language does this PDA recognize?
    • Given a language, come up with the PDA that recognizes it.
    • Does the PDA accept this string?
  • Know how to convert a DFA to a PDA
  • Know how to convert a CFG to a PDA
  • Know that CFGs and PDAs are equivalent in power, and are more powerful than DFAs, NFAs, and REGEXs (recognize the same languages, plus more).