Section 9.5 Formal Languages
789
The preceding grammar allows the erasing productions F S l and A S l.
To generate any language containing l, we have to be able to erase somewhere. In
the following grammar types, we will limit erasing, if it occurs at all, to a single
production of the form S S l, where S is the start symbol; if this production occurs, we will not allow S to appear on the right-hand side of any other productions.
This restriction allows us to crank out l from S as a special case and then get on
with other derivations, none of which allow any erasing. Let’s call this the erasing
convention. The following definition defines three special types of grammars by
further restricting the productions allowed.
A Web browser parses the XML document to determine whether it is a valid instance of the language defined by its associated DTD, and if so, displays it.
Classes of Grammars
Before we identify some types of grammars, let’s look at one more example.
example 57
Let L be the empty string l together with the set of all strings consisting of an
odd number n of 0s, n ≥ 3. The grammar G = (V, V T , S, P) generates L where
V = 50, A, B, E, F, W, X, Y, Z, S6, V T = 506, and the productions are
S S FA
0X S X0
0Z S Z0
S S FBA
Y0 S 0Y
WBZ S EB
FB S F0EB0
FX S F0W
F S l
EB S 0
YA S Z0A
A S l
EB S XBY
W0 S 0W
The derivation S 1 FA 1 * ll = l produces l. The derivation
S 1 FBA
1 F0EB0A
1 F0XBY0A
1
* FX0B0YA
1
* F0W0B0Z0A
1
* F00WBZ00A
1 F00EB00A
1 F00000A
1
* 00000
produces five 0s. Notice how X and Y, and also W and Z, march back and forth
across the strings of 0s, adding one more 0 on each side. This activity is highly
reminiscent of a Turing machine read-write head sweeping back and forth across
its tape and enlarging the printed portion.
ReminDeR
The erasing convention
says how to do erasing
IF erasing is to be done.
It does not require the
production S S l in every
grammar.
789
The preceding grammar allows the erasing productions F S l and A S l.
To generate any language containing l, we have to be able to erase somewhere. In
the following grammar types, we will limit erasing, if it occurs at all, to a single
production of the form S S l, where S is the start symbol; if this production occurs, we will not allow S to appear on the right-hand side of any other productions.
This restriction allows us to crank out l from S as a special case and then get on
with other derivations, none of which allow any erasing. Let’s call this the erasing
convention. The following definition defines three special types of grammars by
further restricting the productions allowed.
A Web browser parses the XML document to determine whether it is a valid instance of the language defined by its associated DTD, and if so, displays it.
Classes of Grammars
Before we identify some types of grammars, let’s look at one more example.
example 57
Let L be the empty string l together with the set of all strings consisting of an
odd number n of 0s, n ≥ 3. The grammar G = (V, V T , S, P) generates L where
V = 50, A, B, E, F, W, X, Y, Z, S6, V T = 506, and the productions are
S S FA
0X S X0
0Z S Z0
S S FBA
Y0 S 0Y
WBZ S EB
FB S F0EB0
FX S F0W
F S l
EB S 0
YA S Z0A
A S l
EB S XBY
W0 S 0W
The derivation S 1 FA 1 * ll = l produces l. The derivation
S 1 FBA
1 F0EB0A
1 F0XBY0A
1
* FX0B0YA
1
* F0W0B0Z0A
1
* F00WBZ00A
1 F00EB00A
1 F00000A
1
* 00000
produces five 0s. Notice how X and Y, and also W and Z, march back and forth
across the strings of 0s, adding one more 0 on each side. This activity is highly
reminiscent of a Turing machine read-write head sweeping back and forth across
its tape and enlarging the printed portion.
ReminDeR
The erasing convention
says how to do erasing
IF erasing is to be done.
It does not require the
production S S l in every
grammar.