Chap ter 2
Con text-Free Gram mars
2.1 INTRODUCTION
2.1.1 Def i ni tion of CFG
A context-free grammar is a 4-tuple (V, T, S, P) where
(i) V is a finite set called the variables
(ii) T is a finite set, disjoint from V, called the terminals
(iii) P is a finite set of rules, with each rule being a variable and a string
of variables and terminals, and
(iv) S V
∈ is the start variable.
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.1.2 Exam ple of CFG
Given a grammar 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
aababb
,
, and
If we assume that a is left paranthesis ‘(’ and b is right paranthesis ‘)’, then
L(G) is the language of all strings of properly nested parantheses.
2.1.3 Right-Lin ear Gram mar
In general productions have the form:
(
)
(
)
*
V T
V T
∪
→
∪
+
.
In right-linear grammar, all productions have one of the two forms:
V
T V
→
*