1-1hit |
CFGs (context-free grammars) with various types of memory are introduced and their generative capacities are investigated. For an automata-theoretic characterization, a new type of automaton called partitioning automaton is introduced and it is shown that the class of languages generated by CFGs with memory type X is equal to the class of languages accepted by partitioning automata of type X.