If u, v and w are strings of variables and terminals and A w
→ is a
rule of the grammar, we say that uAv yields uwv, written uAv uwv
⇒
.
2. Give an example of CFG.
Given a grammar of G
S a b R S
= ({ }, { , }, , ). The set of rules R is
S
aSB
S
SS
S
→
→
→ ∈
This grammar generates strings such as abab, aaabbb and aababb.
3. What is a left linear grammar?
A grammar is which all productions are either of the form
V VT
→
*
or
V
T
→
*
is called a left linear grammar.
4. What is right linear grammar?
A grammar is which all productions are either of the form
V
T V
→
*
or
V
T
→
*
is called a right linear grammar.
5. What do you mean by Parsing?
Finding a derivation of the string is called Parsing.
6. What are derivation trees?
A derivation tree is an ordered tree in which the nodes are labeled
with the left sides of productions and in which the children of a node
represent its corresponding right sides.
7. What do you mean by sentential form?
The resultant of the derivation tree is a word something like
w = aaba for a CFG with productions S
aA A aB B
bB
→
→
→
,
,
,
B
a
→ . This word is said to be in sentential form.
8. Sketch the derivation tree for the CFG given by S
aA A aB
→
→
,
,
B
bB
→ , B
a
→ .
154
Theory of Automata, Formal Languages and Computation
a
b
S
A
B
B
a
a