Lecture 6 CFG & derivation and Pt

Context- Free Grammar
A Context- Free Grammar (CFG) G is a 4-tuple (N,?,R,S), where :
1- N is a finite set of nonterminals or variables.
2- ? is a finite set of terminals.
3- R is a finite set of rules, each consisting of a variables (the left- hand side) and a sentential form (the right- hand side).
4- S is the start symbol.
The binary relation ? on sentential forms is defined as follows:
Let u, v, and w be sentential forms then uAw? uvw iff A?v is a rule in R
? captures a single derivation step.
?* is the reflexive transitive closure of ?,
and L(G)={s??* / S?* s}
Derivations
A sequence of rewritings that transforms the start variable S of a grammar G to a sentence s is called a derivation of s from
G. A derivation in which every derivation step uses the left most variable in the sentential form is called a left most derivation.
A grammar G is called ambiguous if there exist a string s with tow different left most derivations from G.
For example: the arithmetic expression grammar
E?0\1…..\9\(E)\E*E\E+E
Is ambiguous because the sentence
2+3*4 Has tow different left most derivations
E?E*E?E+E*E?2+E*E?2+3*E?2+3*4
E?E+E?2+E?2+E*E?2+3*E?2+3*4
Pars trees
Here is another grammar for arithmetic expressions:
E?T|T+E
T?F|F*T
F?0|1|…|9|(E)
When the start variable is unspecified, it is assumed to be the variable of the first rule in this case E.
This grammar is unambiguous (convince yourself of this fact)