A NOTE ON GRAMMARS WITH COORDINATES.
MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
Pagination or Media Count:
Anderson has defined the notion of a graphical rewriting grammar, in which each production has an associated set of functions that compute coordinates for the symbols in the productions right member in terms of given coordinates of the symbols in its left member. It is shown that any such Anderson grammar AG is equivalent to a one-dimensional AG whose productions are all left-linear thus the power of an AG can be restricted only by restricting its coordinate-computing functions. On the other hand, even if the productions of an AG are left-linear and its functions are all computable by finite automata, its language need not be finite-state or even context-free. Author