**Lecture
8 (Context-Free Grammars), 2/8/18**

**Concepts, definitions (in italics):**

*Context Free Grammar (CFG)*, Formal Definition (pg. 104) tuple (Sigma, V, R, S)*Terminal symbols*(aka characters)*Variables*(aka non-terminal symbols)*Substitution Rules*(aka rules)*Start variable*- A
*derivation*for string w in CFG G is a sequence of replacements where variables get replaced with the right-hand side of a rule, starting with*S*(*G'*s start symbol), until there are no variables left, only terminals - Grammar
*G**generates*a string*w*iff there is a valid derivation for*w*in*G* - Example of
generating a string with CFG: a
^{2n}b^{n} - Example of
generating a string with CFG: wcw
^{R} - The
*length*of a derivation: number of substitutions it contains. - Must be at least one, but there is no upper bound
- The language
*generated*by a CFG*G*: set of all strings generated by*G = L(G)* - Grammars for the languages of the 3 RE base cases
- More examples: strings of even length, strings of odd
length

**Reading:**

- Chapter 2.1 up to middle of p. 107

**Skills:**

- Know new definitions, understand new concepts.
- Given a string
*w*and a CFG*G*, find a derivation for*w*in*G* - Given one step of a derivation in some CFG
*G*, figure out which of the rule was used for this step - Given a
*G*, describe*L(G)*

**Notes:**