11 0 ~ Theory of Computer Science
- - - - - - - - - - - - - - - -
4.1.2 DERIVATIONS AND THE LANGUAGE GENERATED
BY A GRAMMAR
Productions are used to derive one stling over \/N U L from another string.
We give a formal definition of derivation as follows:
Definition 4.2 If a ~ f3 is a production in a grammar G and y, 8 are any
two strings on
U 2:, then we say that ya8 directly derives yf38 in G (we
"\!fite this as ya8 ~ yf38). This process is called one-step derivation. In
G
particular. if a ---1 f3 is a production. then a ~ f3.
G
Note: If a is a part of a stling and a ~ f3 is a production. we can replace
a by f3 in that string (without altenng the remaining parts). In this case we
say that the string we started with directly derives the new string.
For example,
G = US}. {O. I}, {S -t 051. S -t Ol}, 5)
has the production 5 ---1 OS1. So, 5 in 04S1
4 can be replaced by 051. The
resulting string is 0
4 0511". Thus. we have 0
4 51"+ ~ 0"OS11
4 .
G
Note: ~ induces a relation R on IVy U 2:)*. i.e. aRf3 if a ~ [3.
G
G
Defmition 4.3 If a and f3 are strings on \/v U :E, then we say that a derives
~,
' "
f3 if a ~ f3. Here ~ denotes the reflexive-transitive closure of the relation ~
G
G
G
in (Fy U :E)* (refer to Section 2.1.5).
Note: We can note in particular that a 7 a. Also, if a 7 f3. [X ' 1' = f3, then
there exist strings [Xl- a2, .. " (tll' where II ;::: 2 such that
(X = (X] ~ a2 ~ a 3 . .. ~ all = f3
G
G
G
When a ~ f3 is in n steps. we write a b f3.
G
G
Consider. for example. G = ({5}, {O. I}. {S -t OSl, 5 -t OIl, 5).
*
As S ~ 051 ~ 02S1
2 ::::? 03S1 3 , we have S ~ 03S1 3 . We also have
G
G
G
G
0
3 51
3
~ 0 3 51
3 (as (X ~ a).
G
G
Definition 4.4 The language generated by a grammar G (denoted by L(G)) is
defined as {w E :E* IS 7 H}. The elements of L(G) are called sentences.
Stated in another way, L( G) is the set of all terminal strings derived from
the start symbol S.
Definition 4.5 If 5 ,;, ex, then a is called a sentential form. We can note
G
that the elements of L(G) are sentential forms but not vice versa.
- - - - - - - - - - - - - - - -
4.1.2 DERIVATIONS AND THE LANGUAGE GENERATED
BY A GRAMMAR
Productions are used to derive one stling over \/N U L from another string.
We give a formal definition of derivation as follows:
Definition 4.2 If a ~ f3 is a production in a grammar G and y, 8 are any
two strings on
U 2:, then we say that ya8 directly derives yf38 in G (we
"\!fite this as ya8 ~ yf38). This process is called one-step derivation. In
G
particular. if a ---1 f3 is a production. then a ~ f3.
G
Note: If a is a part of a stling and a ~ f3 is a production. we can replace
a by f3 in that string (without altenng the remaining parts). In this case we
say that the string we started with directly derives the new string.
For example,
G = US}. {O. I}, {S -t 051. S -t Ol}, 5)
has the production 5 ---1 OS1. So, 5 in 04S1
4 can be replaced by 051. The
resulting string is 0
4 0511". Thus. we have 0
4 51"+ ~ 0"OS11
4 .
G
Note: ~ induces a relation R on IVy U 2:)*. i.e. aRf3 if a ~ [3.
G
G
Defmition 4.3 If a and f3 are strings on \/v U :E, then we say that a derives
~,
' "
f3 if a ~ f3. Here ~ denotes the reflexive-transitive closure of the relation ~
G
G
G
in (Fy U :E)* (refer to Section 2.1.5).
Note: We can note in particular that a 7 a. Also, if a 7 f3. [X ' 1' = f3, then
there exist strings [Xl- a2, .. " (tll' where II ;::: 2 such that
(X = (X] ~ a2 ~ a 3 . .. ~ all = f3
G
G
G
When a ~ f3 is in n steps. we write a b f3.
G
G
Consider. for example. G = ({5}, {O. I}. {S -t OSl, 5 -t OIl, 5).
*
As S ~ 051 ~ 02S1
2 ::::? 03S1 3 , we have S ~ 03S1 3 . We also have
G
G
G
G
0
3 51
3
~ 0 3 51
3 (as (X ~ a).
G
G
Definition 4.4 The language generated by a grammar G (denoted by L(G)) is
defined as {w E :E* IS 7 H}. The elements of L(G) are called sentences.
Stated in another way, L( G) is the set of all terminal strings derived from
the start symbol S.
Definition 4.5 If 5 ,;, ex, then a is called a sentential form. We can note
G
that the elements of L(G) are sentential forms but not vice versa.