A survey on this subject can be found in. This paper, much work have been done in studying properties of picture languages recognized by finite-state machines and several other models have been designed.
two-dimensional array language (which is not true any longer when using context-free two-dimensional array productions only). Whereas in the string case programmed grammars without appearance checking, matrix grammars without appearance checking, and ordered grammars using arbitrary context-free productions cannot generate every recursively enumerable string language, in this paper we show that (two-dimensional) programmed array grammars without appearance checking, matrix array grammars without appearance checking, and ordered array grammars using #-context-free two-dimensional array productions can already generate any r.e. Yet if we consider #-context-free array productions with the left hand side consisting of one non-terminal symbol surrounded by some blank symbols #, but with no restrictions imposed on the right hand side, then in contrast to the string case these #-context-free two-dimensional array productions are more powerful than the restricted monotonic context-free array productions usually considered in the literature. for short) two-dimensional array languages form a Chomsky-like hierarchy. The families of regular, context-free, monotonic, and recursively enumerable (r.e. Like in the string case, also for two-dimensional array grammars we obtain regular, context-free, and monotonic grammars by imposing specific restrictions on the corresponding array productions. As an application, certain floor-design patterns are generated using such an array P system.
The theoretical model developed is for handling the application problem of generation of patterns encoded as picture arrays over a finite set of symbols. It is shown that this new model of array P system can generate picture array languages which cannot be generated by many other array grammar models. The generative power of such a system is investigated by comparing with the generative power of certain related picture array grammar models introduced and studied in two-dimensional picture language theory. A new picture array model of array generating P system with a restricted type of picture insertion rules and picture array objects in its regions, is introduced here. Among its several variants, string or array language generating P systems involving rewriting rules have been considered. In the bio-inspired area of membrane computing, a novel computing model with a generic name of P system was introduced around the year 2000.
We also examine the effect of regulating the rewriting in a (r / d)P2DCFG by suitably adapting two well-known control mechanisms in string grammars, namely, control words and matrix control. Unlike the case of string context-free grammars, the picture language families of P2DCFG and the two variants (l / u)P2DCFG and (r / d)P2DCFG are mutually incomparable, although they are not disjoint.
The resulting grammar is called (r / d)P2DCFG and rewrites in parallel all the symbols only in the rightmost column or the lowermost row of a picture array by a set of context-free type rules. In this paper we introduce another variant of P2DCFG that corresponds to “rightmost” rewriting in string context-free grammars. P2DCFG and a variant called (l / u)P2DCFG, which was recently introduced motivated by the “leftmost” rewriting mode in string context-free grammars, have been investigated for different properties. This 2D grammar uses only one kind of symbol as in a pure string grammar and rewrites in parallel all the symbols in a column or row by a set of context-free type rules. Pure two-dimensional context-free grammar (P2DCFG) is a simple but effective non-isometric 2D grammar model to generate picture arrays.
0 kommentar(er)
