**Lecture
9 (****CFG
Properties****), 9/27/17 **

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

*Parsing*: given string*s*and grammar*G*, constructing parse tree for*s*in*G*- Example: 2
parse trees for arithmetic expressions with + and *
- Relation to lexing (numbers turn into NUM token)
- Connection between parse trees and expression
evaluation
- Flattening a parse tree into a derivation
- A derivation corresponds to a unique parse tree
- A parse tree may correspond to multiple derivations ,
but there is exactly one
*rightmost*, and one*leftmost*among them.

·
Grammar *G *(with start state S) *generates*
a string *w* iff

o there is a valid *derivation* for *w* in *G *starting at S

- there is a valid
*parse tree*for*w*in*G*rooted at*S* - The language
*generated*by a CFG*G*: set of all strings derived by*G = L(G)* - Two grammars are
*equivalent*iff they generate the same language. *Ambiguous*grammars (different parse trees, or different leftmost derivations for the same string)- The simple
CFG for the language of arithmetic expressions is ambiguous; programming
languages would use a different
CFG
for it which is not ambiguous.
- Unambiguous
grammar for arithmetic expressions with + and * (which only creates
correct parse trees)
*Inherently ambiguous CFL:*all grammars for it are ambiguous- Other ways to
transform grammars (into an equivalent one):
- Only 1 rule
with start symbol
- There are no
terminals in any rules, except for rules of the form V -> c
- All rules
have 2 or less symbols on right-hand side
- Do 3
*constructions* - Given CFGs
*G*and_{1}*G*, we can construct a CFG_{2}*G*such that L(_{0}*G*) = L(_{0}*G*) U L(G_{1}_{2}) - Given CFGs
*G*and_{1}*G*, we can construct a CFG_{2}*G*such that L(_{0}*G*) = L(_{0}*G*) o L(G_{1}_{2}) - Given CFGs
*G*and_{1}*G*, we can construct a CFG_{2}*G*such that L(_{0}*G*) = L(_{0}*G*)*_{1} - Each of the
constructions involves making the
variables disjoint, combining together existing grammars, then creating a
new start state and adding one or two new rules involving this state and
the original start states of
*G*and_{1}*G*._{2} - Theorem: The class of Context Free Languages is
*closed*under: - Union
- Concatenation
- Star
- This follows directly from the 3 constructions above
- Theorem: The class of Regular Languages is a
*proper (or strict) subset*of the class of Context Free Languages - Part 1. Proved
by recursion (induction) that all regular languages are context free,
using the above three constructions.
- Part 2. Proved
by finding a CFL that’s not regular (did in class last time)
- NOTE: The class of Context Free Languages is
*not closed*under: - Intersection
- Complement

(we will prove it later, when we get our hands on some non-CF
languages)

**Reading:**

- Chapter 2.1 up to end of p. 108

**Skills:**

- Know new definitions, understand new concepts.
- Given a string
*w*and a CFG*G,*create a parse tree for*w*in*G* - Show that a
given grammar G is ambiguous (i.e. find a string in L(G)
with more than one parse tree).

·
Do the proofs for Part 1 of above
theorem for homework.

·
Given a RE, create an equivalent CFG
(including homework problem)

**Notes:**

- If two grammars share variables, we can rename the
variables for one or both of the grammars so the variables are disjoint.