Chapter 4: Formal Languages ~ 111
Definition 4.6 G i and G: are equivalent if L(GJ = L(G:).
Remarks on Derivation
1. Any derivation involves the application of productions. When the
number of times we apply productions is one, we write a =? {3; when
. , .
e
it is more than one, \ve \vrite CY. ~ f3 (Note: a ~ a).
e
G
") The string generated by the most recent application of production is
called the working string.
3. The derivation of a string is complete when the working string cannot
be modified. If the final string does not contain any variable. it is a
sentence in the language. If the final string contains a variable. it is a
sentential form and in this case the production generator gets 'stuck'.
NOTATION: (i) We \vrite CY. ~ {3 simply as CY. :b {3 if G is clear from the context.
e
(ji) If A ~ CY. is a production where A E Vv, then it is called an
A-production.
(iii) If A ~ ai' A. ~ a:. .. nA. ~ CY.!/! are A-productions. these
productions are written as A ~ ai i CY.: j ... I am'
We give several examples of grammars and languages generated by them.
EXAMPLE 4.2
If G = ({5}. {a. I}. {5 ~ 051, s ~ A}. S). find L(G).
Solution
As 5 ~ A is a production. S =? A. So A is in L(G). Also. for all n :::: 1.
G
=? 0"51" =? 0"1"
G
G
Therefore.
0"1" E L(G) for n :::: a
(Note that in the above derivation, S ~ 051 is applied at every step except
in the last step. In the last step, we apply 5 ~ A). Hence, {O"I" In:::: O} ~ UG).
To show that L( G) ~ {O''1'' i 17 :::: A}. we start with ].V in L(G). The
derivation of It' starts with 5. If S ~ A is applied first. we get A. In this case
].V =A. Othenvise the first production to be applied is 5 ~ 051. At any stage
if we apply 5 ~ A, we get a terminal string. Also. the terminal string is
obtained only by applying 5 ~ A. Thus the derivation of IV is of the foml
l.e.
5 =? 0
11 51" =? 0"1"
G
G
for some n :::: 1
Definition 4.6 G i and G: are equivalent if L(GJ = L(G:).
Remarks on Derivation
1. Any derivation involves the application of productions. When the
number of times we apply productions is one, we write a =? {3; when
. , .
e
it is more than one, \ve \vrite CY. ~ f3 (Note: a ~ a).
e
G
") The string generated by the most recent application of production is
called the working string.
3. The derivation of a string is complete when the working string cannot
be modified. If the final string does not contain any variable. it is a
sentence in the language. If the final string contains a variable. it is a
sentential form and in this case the production generator gets 'stuck'.
NOTATION: (i) We \vrite CY. ~ {3 simply as CY. :b {3 if G is clear from the context.
e
(ji) If A ~ CY. is a production where A E Vv, then it is called an
A-production.
(iii) If A ~ ai' A. ~ a:. .. nA. ~ CY.!/! are A-productions. these
productions are written as A ~ ai i CY.: j ... I am'
We give several examples of grammars and languages generated by them.
EXAMPLE 4.2
If G = ({5}. {a. I}. {5 ~ 051, s ~ A}. S). find L(G).
Solution
As 5 ~ A is a production. S =? A. So A is in L(G). Also. for all n :::: 1.
G
=? 0"51" =? 0"1"
G
G
Therefore.
0"1" E L(G) for n :::: a
(Note that in the above derivation, S ~ 051 is applied at every step except
in the last step. In the last step, we apply 5 ~ A). Hence, {O"I" In:::: O} ~ UG).
To show that L( G) ~ {O''1'' i 17 :::: A}. we start with ].V in L(G). The
derivation of It' starts with 5. If S ~ A is applied first. we get A. In this case
].V =A. Othenvise the first production to be applied is 5 ~ 051. At any stage
if we apply 5 ~ A, we get a terminal string. Also. the terminal string is
obtained only by applying 5 ~ A. Thus the derivation of IV is of the foml
l.e.
5 =? 0
11 51" =? 0"1"
G
G
for some n :::: 1