Abstract
Ph.D. (Computer Science)
Traditionally a formal language can be characterized in two ways: by a
generative device (a grammar) and an acceptive device (an automaton). The
characterization of two- and three-dimensional Random Context Grammars by
two- and three-dimensional Random Context Automata are investigated.
This thesis is an attempt to progressively extend a certain class of
grammars to higher dimensions where the class of languages generated in
each dimension is contained in the class of languages generated in the next
higher dimension.
Random Context Array Automata which characterizes Random Context Array
Grammars (Von Solms [4,5]) are defined. The power of both Random Context
Array Grammars and Random Context Array Automata is inherent in the fact that
the replacement of symbols in figures is subject to horizontal, vertical and
global context. A proof is given for the equivalence of the class of
languages generated by Random Context Array Grammars and the class of
languages accepted by Random Context Array Automata.
The two-dimensional Random Context Array Grammars are extended to three
dimensions. Random Context Structure Grammars generate three-dimensional
structures. A characteristic of Random Context Structure Grammars is that the
replacement of symbols in a structure is subject to seven relevant contexts.
Random Context Structure Automata which characterize Random Context
Structure Grammars are defined. It is shown that the class of languages
generated by Random Context Structure Grammars are equivalent to the class
of languages accepted by Random Context Array Automata...