Rule 18

The generation evolving from the regular expression according to Rule 18 is which can be simplified slightly to If we calculate derivatives strictly according to the rules, simplifying only to remove 's (% in the following script) and terms beginning with 's (#'s), we obtain for the first few derivatives

(00*(0+10*1))*/0= (0*(0+10*1))(00*(0+10*1))*
(00*(0+10*1))*/1= #
(00*(0+10*1))*/00= (0*(0+10*1)+%)(00*(0+10*1))*
(00*(0+10*1))*/01= (0*1)(00*(0+10*1))*
(00*(0+10*1))*/10= #
(00*(0+10*1))*/11= #
(00*(0+10*1))*/000= (0*(0+10*1)+%)(00*(0+10*1))*+(0*(0+10*1))(00*(0+10*1))*
(00*(0+10*1))*/001= (0*1)(00*(0+10*1))*
(00*(0+10*1))*/010= (0*1)(00*(0+10*1))*
(00*(0+10*1))*/011= (00*(0+10*1))*
(00*(0+10*1))*/100= #
(00*(0+10*1))*/101= #
(00*(0+10*1))*/110= #
(00*(0+10*1))*/111= #

If we introduce the definitions

we may draw the conclusion that there are only five distinct derivatives, one of which is zero, and one of which is a sum. Thus the following table is sufficient to deduce all the remaining derivatives.

The five distinct derivatives are also the nodes in a diagram describing the second generation of Rule 18; it is an exit diagram, whose links are shown in Figure . Comparison with Figure shows them to be equivalent, although slightly different.

 
Figure: Exit diagram for Rule 18. 

The right factors will be formed from intersections of these left derivatives.

It is possible to work out the right derivatives of this same regular expression; One might think that the results should be the same because Rule 18 is a symmetrical rule. However, the regular expression describing it is not, and consequently the remainder of the analysis must proceed accordingly. We can use the same program to calculate the derivatives, however, just by reversing the order of the factors:

 
((0+10*1)0*0)*/0= (0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/1= ((0*1)0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/00= (0*0+%)((0+10*1)0*0)*
((0+10*1)0*0)*/01= #
((0+10*1)0*0)*/10= ((0*1)0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/11= (0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/000= (0*0+%)((0+10*1)0*0)*+(0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/001= ((0*1)0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/010= #
((0+10*1)0*0)*/011= #
((0+10*1)0*0)*/100= ((0*1)0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/101= (0*0)((0+10*1)0*0)*
((0+10*1)0*0)*/110= (0*0+%)((0+10*1)0*0)*
((0+10*1)0*0)*/111= #

This time we define

obtain the derivatives

and the entrance diagram

While different from the exit diagram, it evidently serves the same purpose. To use an entrance diagram one builds up an expression from right to left reading backwards along the arrows until an initial node is reached.