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).