Context-Sensitive Systems

As already mentioned at the beginning of this chapter, in a context-sensitive system the use of a production is made dependent on the local environment of a character. The left side of a production now has the form rAv, where r, v є V + and a є V. With this type of system, it becomes problematic if several productions with differently sized contexts can be applied to one character. In order to yield a well-defined approach, additionally it is defined that the production with the largest context is used first in such a situation. Traditionally, in connection with L-systems a context-sensitive rule is indi­cated in the format т < A > и ::= b. In contrast to the Chomsky notation, rav ::= b the context is here explicitly defined. We know what in a production is the active part that is to be replaced. A simple example is a system for the movement of a character (a signal) within a string: Let w = baaaaaaa and

P = {b < a ::= b, b ::= a}. The result is the following sequence of strings:

baaaaaaa

abaaaaaa

aabaaaaa

aaabaaaa

aaaabaaa

Here, the character moves through the string from left to right. Such signal characters can control the growth in parts of the plant, such as the successive blooming of blossoms in a large flower stand, or they can influence the wither­ing of subtrees in a larger tree.

Context-Sensitive Systems

Figure 5.8

Branching structures generated using context-sensitive L-systems by Hogeweg and Hesper [88] (Image courtesy of P. Prusinkiewicz)

 

Context-Sensitive SystemsContext-Sensitive Systems

Part

(a)

(b)

(c)

n

30

24

26

5

22.50

25.75

22.50

Ignore:

+-F

+-F

+-F

и

F1F1F1

F0F1F1

F1F1F1

A

о

V

о

0 :: =

1

1

0

Л

о

V

о

1 :: =

1[-F1F1]

0

1[-F1F1]

0 < 1 >

0 :: =

1

0

1

0 < 1 >

1 :: =

1

1F1

1

1<0>

0 :: =

0

1

0

1<0>

1 :: =

1F1

1[+F1F1]

1F1

1<1>

0 :: =

1

1

1

1<1>

1 :: =

0

0

0

* < – >

* ::=

* < + >

* ::=

+

+

+

If branching structures are treated, then the mechanism must ignore the parts included in the parentheses for the determination of the context, because oth­erwise the structural context of the characters cannot be found. Also, special

characters should be ignored for controlling the geometrical interpretation; this is indicated together with the definition of the system.

In Fig. 5.8 several context-sensitive branching structures are shown. The results originate from a work by Hogeweg and Hesper [88] in which systematically a number of relatively simple context-sensitive systems were analyzed. Smith [201] later refined the graphical representation. The illustrations are taken from [166].

Подпись: exceptionsПодпись: indexingWhen comparing the systems in Fig. 5.8, it is noticeable that the systems (a) and (c) are very similar, although the produced structures have very different appearances. This also explains why the results were obtained only using a systematic search. Nevertheless, it is unquestionable that only with context- sensitive systems processes such as signal distributions can be modeled in plants. However, at least for the definition of branching structures there seem to be alternatives. With exception rules and indexed items that assign an unique identification number at any time to each of the produced partial objects, simi­lar results can be obtained (see Sect. 6.5).

However, such an indexing has the disadvantage that in an animation the num­ber of objects in a plant can change and that then also the indices are again newly assigned, at least if the indexing is done automatically. This again would cause the exceptions (inasmuch as they are marked by indices) to affect other parts of the objects, which must be avoided at all cost. To the reader perhaps this appears as an unimportant detail problem; nevertheless, there are a number of consequences for practical work. Therefore, index-free L-systems have here a primary advantage.