Graph-Controlled Grammars as Language Acceptors

In this paper, we study the concept of accepting grammars within various forms of regulated grammars like programmed grammars, matrix (set) grammars, grammars with regular (set) control, periodically time-variant grammars as variants of grammars controlled by bi-coloured digraphs. We focus on their descriptive capacity. In this way, we continue our studies of accepting grammars 1, 2, 3, 11, 13, 14, 15]. Periodically time-variant grammars yield the rst example of a non-trivial equivalence of generating and accepting mode in the absence of appearance checkings. Supported by Deutsche Forschungsgemeinschaft grant DFG La 618/3-1.