Exam 2 Topics - Fall 2015

  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) [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 PDA accepts and rejects a string and accepts a language.
    2. Describe the difference in components and operation between a PDA, a DFSM, and/or a NDFSM
    3. Describe the parts in the formal definition of a PDA and a configuration and computation

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

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

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

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

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

    12. 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:

    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

    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 Lemma is used to prove.
    2. Explain why long strings are pumpable.
    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.