**Lecture
8 (Context-Free Grammars), 9/25/17**

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

- Another example of using the Pumping Lemma to prove
that a language is not regular

o *ww* over alphabet {a,b, …, z} is not
regular [proven by Pumping Lemma, choose string **a**^{p} **b a ^{p}**

·
Explanation
of the *negation* of the Pumping Lemma
Property

*Context Free Grammar (CFG)*, Formal Definition (pg. 104)*Variables*(aka non-terminal symbols)*Terminal symbols*(aka characters)*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: 0
^{n}1^{n} - The
*length*of a derivation: number of substitutions it contains. - The language
*generated*by a CFG*G*: set of all strings generated by*G = L(G)* - A language
*L*is_{0}*context-free*iff there is some*context-free grammar**G*such that*L*= L(_{0 }*G*) - Last time we
showed that {0
^{n }1^{n }: n >= 0} is not a regular language; today we saw that it is a context-free language (CFL). - Why called context-free?
- More examples: simple arithmetic, strings of odd length
- The names of CFG
variables are meaningless, can always replace any name by a different
(new) name without changing the language of the grammar -- like local
variables in a procedure.
*Leftmost*derivations,*rightmost*derivations*Parse Trees: internal nodes =*variables*, leaves =*terminals,*root*= start variable*For every derivation, there is a corresponding parse tree*- Carries the same information, except for the order of
substitutions
*Applications*of parse trees:- compilers/interpreters
- Natural Language Processing

**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 string CFG
*G*and a derivation in G for some string*w*, construct a parse tree that corresponds to this derivation - Given a
*G*, describe*L(G)* - Given a description of a language, show that it is
context-free (i.e. create a CFG for it).

**Notes:**