Reactivity and Grammars: An Exploration

We consider the relationship between grammars and formal languages, exploring the following idea: Normally, when considering the process of deriving a string using a grammar, all structures remain xed except for the string which is changed only by replacement of substrings. By introducing a more dynamic view of this process, we may allow the grammar to change in various ways as the derivation proceeds, or we may change the notion of application of a rule to a string, or the intermediate strings may be modied between application of rules. We call these more dynamic approaches to language generation 'reactive grammars' and explore, in this paper a range of such reactivities. Some of these are related to previously introduced notions of generative grammars, others appear to be new. Reactivity of computational structures has been explored in other areas, e.g. in Kripke structures and in the general areas of evolvable and adaptive systems.