Topics #1: Context Free Grammar (CFG)
• Know the formal definition of a CFG, namely the 4-tuple of (𝑉, Σ, 𝑅, 𝑆) • Know the definition of the following terminologies:
a) Variables of a grammar G
b) Terminals of a grammar G
c) A grammar generates a language L.
d) A string x is derived from a grammar G.
e) A rule R yields a string x.
• Given a CFG, be able to show step-by-step derivation of a string 𝑠 ∈ 𝐿
• Given a CFG and a string 𝑠 ∈ 𝐿 , be able to draw a parse tree for the derivation of the
string.
• Given a CFG, be able to identify (describe in English) what language it generates.
• Be able to list a few languages that is context-free, but not regular.
• Given a language described in English, be able to give a CFG that generates it.
• Know how to construct a CFG from two or more than two simpler CFGs by using the
union (U) or concatenation (∘) operators.
• Given a deterministic finite automata (DFA), know the algorithm of getting a CFG that
generates the same language and vice versa, i.e. given a CFG that is generated from a
DFA, be able to draw the DFA’s state diagram from it.
• Know the definition of left-most derivation.
• Given a CFG, be able to identify whether it’s ambiguous or not. i.e. know the definition
of ambiguity of a CFG.
• Know the definition of Chomsky Normal Form (CNF). Given a CFG, be able to identify
whether it’s in CNF or not.
• Given a CFG, be able to apply the algorithm we learned to convert it into CNF.
• Know that CFL are closed under union (U), concatenation (∘) and Kleene star(⋆).
Know how we proved this by constructing a new CFG from it.
• Know that CFL are NOT closed under intersection (∩) or complement ( ̅ )
• Know that all regular languages are also context free, i.e. 𝑅𝐿 ⊑ 𝐶𝐹𝐿
Topics #2: Pushdown Automata (PDA)
• Know the formal definition of a PDA, namely the 6-tuple (𝑄, Σ, 𝛤, 𝛿, 𝑞0, 𝐹).
• Know a PDA is actual a FA with a stack.
• Know the transition function of a PDA is defined as 𝛿: 𝑄 × Σ𝜀 × Γ𝜀 ⟶ 𝑃(𝑄 × Γ𝜀)
• Given CFL languages, such as 𝐿 = {0𝑛1𝑛| 𝑛 ≥ 0}, be able to draw the state diagram of
the PDA that recognizes the language.
• Know the definition of a PDA’s computation. Given a non-deterministic PDA and a string s, be able to tell whether this PDA accepts or rejects s.
• Know that PDA and CFG are equivalent in computation power, both are capable of describing the CFL.
• Understand Lemma 2.21: if a language L is context free, then some pushdown automaton recognizes it.
1
• Given a CFG, be able to apply the algorithm learned to create a non-deterministic PDA that recognize it (be able to draw the state diagram of the PDA)
• Understand Lemma 2.27: if a pushdown automata recognize some language L, then L is context free.
• Given a PDA’s state diagram, be able to apply the algorithm we learned to get rules in the corresponding CFG.
Topics #3: Non-Context-Free Languages (Pumping Lemma)
• For some commonly seen languages, be able to identify that they are NOT context free.
• Know the property of all context free languages, i.e. for certain strings s € L, as long as
|s| ≥ P (pumping length), they all can be divided into 5 parts that satisfy the 3
conditions.
• Be able to describe the pumping lemma clearly.
• Be able to apply pumping lemma to prove that certain languages are not context free.
Topics #4: Turing Machine Intro. (TM)
• Be able to describe the general structure of a TM.
• Know the similarities or differences between a TM with a FA or a PDA.
• Know the formal definition of a TM, namely 7-tuple of (𝑄, Σ, 𝛤, 𝛿, 𝑞0, 𝑞𝑎𝑐𝑐𝑒𝑝𝑡, 𝑞𝑟𝑒𝑗𝑒𝑐𝑡)
• Know the transition function of a TM is 𝛿: 𝑄 × Γ ⟶ 𝑄 × Γ × {𝐿, 𝑅}
• Know the definition of a configuration in a TM.
• Know what an accepting, rejecting, halting or starting configuration is.
• Given the state diagram of a TM and a string s, be able to show the sequence of
configurations that from starting configuration to accepting/rejecting configuration on s.
2