84 CHAPTER 4: IMPROVING THE GRAMMAR

S fi CEJLIJOMNIGPOPDf
A fi f[
B fi DA
C fi IF
D fi f]
E fi B+
F fi B-
G fi HK
H fi CD
I fi A+
J fi GM
K fi EF
L fi EH
M fi FG
N fi FH
O fi DKLK
P fi NK

f[f]f[
f[+f]f[?
f]f]f[+
f]f[?
f[+f]f[?f]f]f[+f]f[?
f[+f]f[?f]
f[+
f[+f]f[?f]f]f[+f]f[?f]f[?f[+f]f[f]f]f[+f]f[?
f]f[+f]f[?
f]f[+f[+f]f[?f]
f]f[?f[+f]f[?f]f]f[+f]f[?
f]f[?f[+f]f[?f]
f]f]f[+f]f[?f]f[+f[+f]f[?f]f]f[+f]f[?
f]f[?f[+f]f[?f]f]f[+f]f[?

Figure?4.5 The grammar produced by SEQUITUR from the sequence in Figure?4.3b, step 3

The first step in remedying these problems is to restate the L-system in a nonrecursive way. Because it is recursive, and there is no distinction between terminal and non-terminal symbols, it is necessary to specify the number of times the rewriting rule is applied in order to generate a sequence. Choosing three steps results in the right-most sequence in Figure?4.3b. A recursive L-system along with a derivation length has an equivalent non-recursive version, which is shown for each derivation step in Figure?4.3d. Each non-recursive grammar reproduces the same sequence as the recursive version evaluated to that number of steps, and also maintains a resemblance to the original grammar. In Section 6.1, this resemblance will be exploited to form a recursive version from the non-recursive one, but for now the aim will be for SEQUITUR just to reproduce the non-recursive version.

Producing a non-recursive version for a particular number of derivation steps solves two of the three difficulties in the original grammar: as a by-product of producing a non-recursive grammar, the grammar can now be interpreted as a Chomsky grammar, treating f as a terminal symbol, as it no longer heads a rule. The third difficulty is that the L-system does not obey the digram uniqueness constraint. This can be remedied in two ways, by replacing either A[ or A]A (or the equivalent sequence in the other rules) with a rule. The result of the second, more compressive replacement is shown in Figure?4.3e for each level of evaluation.

The grammars are now in a form compatible with SEQUITUR?s output, and the question of SEQUITUR?s ability to reproduce such modified L-systems can now be addressed. Figure?4.5 shows the grammar produced by SEQUITUR given the sequence in Figure?4.3b at the third derivation step. The second column in Figure?4.5 gives