The set of all strings obtained by using Production rules is the “Language”
generated by the Grammar.
If the grammar G = (V, T, S, P) then
L G
w T S
w
( ) {
:
}
*
*
= ∈
⇒
If W L G
∈ ( ), then the sequence
S
w
w
w
w
w
n
⇒ ⇒
⇒
⇒
⇒
1
2
3 KK
is a “derivation” of the sentence w.
The string S w w
w n
, , ,
,
1
2 KK
which contain variables as well as
terminals, are called “SENTENTIAL FORMS” of the derivation.
Ì Exam ple 0.1.52: Given a Grammar
(
)
G
S
a b S P
= { }, { , }, ,
with P defined as
S
aSb
S
→
→
,
λ
(i) Obtain a sentence in language generated by G and the sentential form
(ii) Obtain the language L(G).
Solu tion
S
aSb
aaSbb
aabb
⇒
⇒
⇒
Therefore we have S
aabb
⇒
*
.
(i) Sentence in the language generated by G = aabb.
Sentential form = aaSbb.
(ii) The rule S
aSb
→
is recursive.
All sentential forms will have the forms
w a S b
i
i
i
=
Applying the production rule S
aSb
→
, we get
a S b
a S b
i
i
i
i
⇒
+
+
1
1
This is true for all i.
In order to get a sentence we apply S → λ.
Therefore we get
S
a S b
a b
n
n
n n
⇒
⇒
*
38
Theory of Automata, Formal Languages and Computation