An L-System is a description of a formal grammar in which all tokens in the input are concurrently transformed by their respective productions. Conversely, a Chomsky Grammar is a description of a formal grammar in which all tokens in the input are sequentially transformed by their respective productions.

 

For example, in the context-free grammar:

A ---> B

B ---> AB

 

With axiom "A" the L-System produces this tree.        While the Chomsky grammar produces this tree.

 

 

 

If we get our output by concatenating the leaf nodes of each tree into a string, the L-System produces the output "BAB", while the Chomsky Grammar produces the output "BAB". Since "BAB" is equivalent to "BAB", the two grammars produce the same output. However, the Chomsky grammar takes one more iteration over the input to produce it's output.

 

This last statement is an interesting discovery: if the complexity of the L-System is O(1) and the complexity of the Chomsky Grammar is O(n) then, for large inputs, the L-System will produce the same result much faster. If this is true, that would mean that most programs which transform their input stand to gain significant performance improvements by defining them as L-Systems rather than as Chomsky Grammars. Which leads to the importance of finding a proof for the conjecture:

 

L-Systems and Chomsky Grammars define precisely equivalent grammars.

 

As a simple example of their equivalence let's consider a program which takes two inputs, a string A and a character B. The task of the program is to find if the character B exists in the string A. The program is to output a boolean value of true if it finds the character, otherwise it is to output a boolean value of false. As an example, let's run our program with the inputs A="ABDEF" and B='F'. The program could then be defined as the context-free grammar:

 

F ---> true

 

The L-System then produces this graph:                 While the Chomsky Grammar produces this graph:

 

It is immediately apparent that the two produce the same output. It is also immediately apparent that the Chomsky grammar again has a complexity of O(n) while the L-System has a complexity of O(1). In this concrete example, the Chomsky Grammar takes nearly four times as many iterations to produce the same output that the L-System produces in one iteration.

 

Let us now consider a similar program. This time with two inputs, a string A and a string B. The task of the program is to find if the string B exists in the string A. If the program finds the string B in the string A it is to output a boolean value of true. Otherwise, if the program does not find the string B in the string A, it is to output a boolean value of false. Let us run this program with the example inputs A="ABCDEF" and B="DEF" . This program cannot be defined by a simple context-free grammar. Instead, it's definition requires a right-context-sensitive grammar:

 

D > E ---> x

x > F ---> true

 

The L-System then produces this graph:                 While the Chomsky Grammar produces this graph.

 

What we can gleam from this is that the L-System is again faster. This time, however, the L-Systems complexity is related to the number of non-terminal productions, while the Chomsky Grammars complexity is still related to the size of the axiom. Of course, this reduces the advantage of the L-System as the length of the match string B approaches the length of the string A. However, this can be solved with a left-right-context-sensitive grammar for the same problem:

 

D < E > F ---> true

 

The L-System then yields the graph:                         While the Chomsky Grammar yields the graph:

 

 

While it may appear at first glance that the L-Systems complexity is back to being constant, it's actual complexity is O(n/2) where n is the length of the match string B. The complexity of the Chomsky Grammar is still O(n) where n is the number of characters in the input string A.

 

Interestingly, in each example, the L-System produces a faster solution. Which leads to the conjecture:

 

L-Systems and Chomsky Grammars define the same family of grammars. Additionally, for every problem solvable by defining a grammar, there exists a grammar for which the L-System has a smaller complexity than the equivalent Chomsky Grammar.

 

At first thought, that conjecture may not mean much. Both L-Systems and Chomsky grammars must look at each token in the input. However, by the very definition of L-Systems, each input token can be transformed concurrently. On the other side of the same coin, the definition of Chomsky Grammars states that the tokens cannot be transformed concurrently. As a result, L-Systems not only have an advantage over Chomsky Grammars in that they have a lower complexity, L-Systems also have an advantage over Chomsky Grammars in that they are parallelizable and Chomsky Grammars are not.