Formal modeling grammars.(Viewpoint MODELING)(Viewpoint essay)

The sheer complexity of trees, plants, or cities makes it impossible to model those structures manually for computer graphics applications. To reproduce the rich structure of such formations, procedural techniques are used, most of which are based on a set of very simple rewriting rules. These systems (such as the L-system) are based on formal grammars, a fundamental concept first introduced in linguistics and now studied in a branch of mathematics, the formal language theory.

Formal Languages

Formal and natural languages (such as English) generally have two main aspects: syntax and semantics. The first is what the language "looks like," in so far as what are valid and what are invalid words or sentences; the latter refers to the meaning of various utterances. Formal language theory is only concerned with the syntax of a language and completely ignores meaning. The precise description of a language is called the grammar (or formation rules).

When thinking about the uses of grammars, our first idea usually is the recognition of error for instance, not spelling a word properly or using wrong punctuation. However, grammars are also regarded as a means to generate valid strings of a language. When learning a foreign language, we not only memorize basic words but also a set of rules on how to inflect them or form sentences with them. The rules of grammar help us to create valid utterances of which we may never have even heard.

A formal generative grammar is essentially a set of rules that we can apply to strings (sequences of symbols) to transform them. Triggering an applicable rule one after the other, we can generate any valid combination of words in the language. Generative grammar originates in the work of an American linguist, Noam Chomsky, beginning in the late 1950s. It is considered to be one of the most significant contributions to the field of linguistics made in the 20th century.

[ILLUSTRATION OMITTED]

But why would it be significant to other fields of science, like computer graphics? While in linguistics the alphabet is the set of letters or set of words of a particular language, in other applications of formal grammars we can define an arbitrary alphabet: a set of algae cells, commands of a programming language, or 3D modeling operations. Using such symbols as the building blocks of the language, we have a powerful tool to express very complex structures and patterns. Formal grammars are used to detect erroneous HTML (or XML) code of Web pages, identify syntax problems in computer programs, or to simulate biological formations, such as realistic neural cells.