TOC Chapter 13

Chapter 13. Recent Trends and Applications

13.1. Regulated Re-writing

In a given grammar, re-writing can take place at a step of a derivation by the usage of any applicable rule in any desired place. That is, if A is a nonterminal occurring in any sentential form say αAβ, the rules being A → γ, A → δ, then any of these two rules are applicable for the occurrence of A in αAβ. Hence, one encounters nondeterminism in its application. One way of naturally restricting the nondeterminism is by regulating devices, which can select only certain derivations as correct in such a way that the obtained language has certain useful properties. For example, a very simple and natural control on regular rules may yield a non-regular language.

While defining the four types of grammars in Chapter 2, we put restrictions in the form of production rules to go from type 0 to type 1, then to type 2 and type 3. In this chapter, we put restrictions on the manner of applying the rules and study the effect. There are several methods to control re-writing. Some of the standard control strategies will be discussed below.

13.2. Marcus Contextual Grammars

Marcus defined the contextual grammars in 1969. The implicit motivation for these new generative devices were in the concepts of descriptive linguistics. S. Marcus introduced first what are known as ‘external contextual grammars (ECG)’ and other variants like ‘internal contextual grammars (ICG)’; total contextual grammars were developed later. The power of contextual grammars is compared with Chomskian grammars, and some other grammars (Păun, 1997). The research on this branch of formal language theory is well developed now.

In a CFG, rules are always of the form A → α. One understands that the application of the rules to any word containing A does not depend on the context. That is, any word of the form w₁ Aw₂ will yield w₁αw₂ on application of A → α once, whereas a CFG will contain rules of the form w₁Aw₂ → w₁ αw₂, which are understood to be sensitive to the contexts w₁ and w₂. That is, one cannot apply this rule to any word containing A as in the case of context-free rule. Thus, in the above-said Chomskian models of re-writing, contexts may or may not play a role for re-writing.

13.3. Lindenmayer Systems

L-systems were defined by Lindenmayer in an attempt to describe the development of multi-cellular organisms. In the study of developmental biology, the important changes that take place in cells and tissues during development are considered. L-systems provide a framework within which these aspects of development can be expressed in a formal manner. L-systems also provide a way to generate interesting classes of pictures by generating strings and interpreting the symbols of the string as the moves of a cursor.

From the formal language theory point of view, L-systems differ from the Chomsky grammars in the following three ways:

13.4. Grammar Systems and Distributed Automata

With the need to solve different problems within a short-time in an efficient manner, parallel and distributed computing have become essential. Study of such computations in the abstract sense, from the formal-language theory point of view, started with the development of grammar systems. In classical formal-language theory, a language is generated by a single grammar or accepted by a single automaton. They model a single processor or we can say the devices are centralized. Though multi-tape Turing machines (TMs) try to introduce parallelism in a small way, the finite control of the machine is only one. The introduction of distributed computing useful in analyzing computation in computer networks, distributed databases etc., has led to the notions such as distributed parallelism, concurrency, and communication. The theory of grammar systems and the distributed automata are formal models for distributed computing, where these notions could be formally defined and analyzed.

Grammar Systems

A grammar system is a set of grammars working in unison, according to a specified protocol, to generate one language. These are studied to model distribution, to increase the generative power, to decrease the complexity etc. The study of grammar systems probes into the functioning of such system under specific protocols and the influence of various protocols on various properties of the system are considered.