Communicating grammar system

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

Communicating grammar systems consist of several formal grammars that have a means of communicating with one another. The type of communication depends on the respective system and can expand the generative power of the individual grammars.

Communicating grammar systems can thus be viewed as complex systems , because the interaction of several individual components means that the capabilities of the system are not immediately apparent from the capabilities of the individual components.

Distributed cooperating grammar systems ( c ooperating d istributed G Rammar S ystems / CDGS) and parallel communicating grammar systems ( p arallel c ommunicating G Rammar S ystems / PCGS) are examples of these types of systems.

Models

Blackboard model

A model for the cooperation of distributed cooperating grammar systems is the so-called blackboard model. The knowledge required for processing is distributed to independent agents who all try to solve a problem together on a board. All agents try to solve the problem at the same time and work on the same database, the board. Transferred to grammars, the participating grammars work on a common derivation.

Therefore the control of the agents is an important part of these grammar systems.

Classroom model

The classroom model is a modeling of grammar systems that communicate in parallel. Each agent receives his own notebook that contains the description of a partial problem. Each agent is only allowed to work on its copy. There is a clearly identified agent who can write on the board alone. The agents are allowed to communicate with each other through their notebooks.

Each grammar thus creates its own derivation form, but only the derivation produced by the main grammar solves the problem. How far the individual grammars communicate with each other depends on the respective system.

Generative power

The generative power is increased by the communication depending on the generative power of the individual components.

PCGS from type 3 grammars

Systems made up of three regular grammars that communicate in parallel (type 3 grammars according to the Chomsky hierarchy ) can generate context-sensitive languages .

An infinite hierarchy for the generative power of these systems has been proven. There is a pumping lemma stating that every additional regular grammar in a grammar system leads to new languages ​​that the original system could not yet generate.

Type 1 PCGS

The generative power of context-sensitive grammar is so strong that with the help of grammar systems, depending on the type of communication, two to three components are sufficient to generate all recursively enumerable languages .

literature

• Herbert A. Simon : The Sciences of the Artificial. 2nd edition. MIT Press, Cambridge, MA 1982, ISBN 0-262-69073-X .
• Erzsébet Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. Paun: Grammar Systems. A grammatical Approach to Distribution and Cooperation (= Topics in computer mathematics. 5). Gordon and Breach, Yverdon et al. 1994, ISBN 2-88124-957-4