Exam 2 Topics - Fall 2017




  1. The exam will focus on the following material: Notes and Chapters 11, 12, 16 (skip 14 and 15) and an overview understanding of Pumping Theorems from Chapters 8 and 13

  2. Definitions: Define the following terms and/or expressions and use them appropriately
    1. Context Free Grammar (CFG)
    2. Language of a grammar
    3. Context Free Language (CFL)
    4. Derivation
    5. Derive
    6. Derive in 0 or more steps
    7. Derive Ambiguously
    8. Ambiguous Grammar
    9. Inherently Ambiguous Language
    10. Chomsky Normal Form (CNF) [Not On Exam (NOE)]
    11. PDA M recognizes Language L

  3. Grammar and PDA Symbols - Define the following symbols and use them appropriately:

  4. Grammars

  5. Pushdown Automata (PDA)
    1. Describe when a PDA accepts a string, rejects a string, or does neither.
    2. Define the language that a PDA accepts.
    3. Describe the difference in components and operation between a PDA, a DFSM, and/or a NDFSM
    4. Describe the parts in the formal definition of a PDA and a configuration and computation

    5. Convert between the formal and graphical representations of a given PDA
    6. Identify the correspondences between the formal and graphical representations of a given PDA

    7. Describe the basic operation of a PDA, including how a PDA recognizes a string
    8. Trace the behavior of a given PDA on a given input string

    9. Analyze a PDA to identify the language it recognizes
    10. Create a PDA that recognizes a given language

    11. Create a PDA that recognizes the language of a given CFG, either natural or using the CFG to PDA algorithm.

    12. Describe what it means for a PDA to be deterministic (ie no competing transitions and no competition between accepting and making an empty transition)

    13. Describe 2 ways to reduce nondeterminism in a machine (eg push stack marker and mark end of input), and create a deterministic PDA that uses these techniques.

  6. Parsing

  7. Context Free Languages
    1. State and explain the following listing of the language recognition/generation power of various machines:
      DFSM = NFSM < DPDA < NDPDA = CFG

    2. State and explain the following listing of languages, and give examples of languages in each category:
      Regular Languages < Deterministic Context Free Languages < Context Free Languages < Non-CFL

    3. Use the algorithm given to convert a grammar into an equivalent PDA and explain the significance of this.

  8. Pumping Lemma
    1. Explain what a Pumping Theorem/Lemma (PL) is used to prove (in the context of both Regular and CF PL).
    2. Explain why long strings are pumpable (both regular and CF).
    3. [NOE] State the Pumping Theorem for Regular Languages
    4. [NOE] Use a Pumping Lemma to prove an intuitive proof that a simple language is not Regular/CF.