Regulated rewriting

An important branch of formal language theory, starting from the observation that most natural and artificial languages of interest are non-context-free (cf. Grammar, context-free). By imposing certain restrictions on the derivation in context-free grammars, the generative power is increased, still preserving some of the attractive features of context-free grammars.

There are some dozens of regulating mechanisms of this type: matrix, programmed, random context, regularly controlled, periodically time variant, indexed, state, valence, parallel grammars, grammars controlled by bicoloured digraphs, etc. See [a1] for details; recent information can be found in [a2].

Example.

A programmed grammar (introduced in [a3]) is a construct

$$ G = ( N,T,S,P ) , $$

where $ N $, $ T $ are disjoint alphabets (the non-terminal and the terminal alphabet), $ S \in N $( axiom), and $ P $ is a finite set of quadruples $ ( r : A \rightarrow {x, \sigma ( r ) , \varphi ( r ) } ) $; $ A \rightarrow x $ is a context-free rule over $ N \cup T $, $ r $ is the label of the rule, $ \sigma ( r ) $ and $ \varphi ( r ) $ are sets of labels of rules in $ P $( $ \sigma ( r ) $ is the success field and $ \varphi ( r ) $ is the failure field). Let $ { \mathop{\rm Lab} } $ be the set of all labels of rules in $ P $. For $ ( r,w ) , ( r ^ \prime ,w ^ \prime ) \in { \mathop{\rm Lab} } \times ( N \cup T ) ^ {*} $ one writes $ ( r,w ) \Rightarrow ( r ^ \prime ,w ^ \prime ) $ if one of the following two cases holds:

1) $ w = uAv $ and $ w ^ \prime = uxv $, for $ ( r : A \rightarrow {x, \sigma ( r ) , \varphi ( r ) } ) \in P $, $ u,v \in ( N \cup T ) ^ {*} $, and $ r ^ \prime \in \sigma ( r ) $;

2) $ w $ does not contain the symbol $ A $, for $ ( r : A \rightarrow {x, \sigma ( r ) , \varphi ( r ) } ) \in P $ and $ w = w ^ \prime $, $ r ^ \prime \in \varphi ( r ) $. (Note the way of controlling the sequencing of rules application by means of the mappings $ \sigma $ and $ \varphi $ from $ { \mathop{\rm Lab} } $ to the power set of $ { \mathop{\rm Lab} } $.) The language generated by $ G $ is

$$ L ( G ) = $$

$$ = \left \{ {w \in T ^ {*} } : {( r,S ) \Rightarrow ^ {*} ( r ^ \prime ,w ) \textrm{ for some } r,r ^ \prime \in { \mathop{\rm Lab} } } \right \} , $$

where $ \Rightarrow ^ {*} $ is the reflexive and transitive closure of the relation $ \Rightarrow $. Let $ { \mathop{\rm PR} } _ {\textrm{ ac } } ^ \lambda $ be the family of languages of this form; when $ \lambda $- rules are not allowed, one writes $ { \mathop{\rm PR} } _ {\textrm{ ac } } $. When $ \varphi ( r ) = \emptyset $ for all rules in $ P $, one says that the grammar is without appearance checking; the corresponding families of languages are denoted by $ { \mathop{\rm PR} } ^ \lambda $, PR. Denote by CF, CS, and RE the families of context-free, context-sensitive, and recursively enumerable languages, respectively. Then:

1) $ { \mathop{\rm CF} } \subset { \mathop{\rm PR} } \subset { \mathop{\rm PR} } ^ \lambda \subset { \mathop{\rm RE} } $, $ { \mathop{\rm PR} } \subset { \mathop{\rm PR} } _ {\textrm{ ac } } \subset { \mathop{\rm CS} } \subset { \mathop{\rm PR} } _ {\textrm{ ac } } ^ \lambda = { \mathop{\rm RE} } $;

2) $ { \mathop{\rm PR} } _ {\textrm{ ac } } $ is an abstract family of languages (cf. also Trio).

References

[a1]	J. Dassow, Gh. Păun, "Regulated rewriting in formal language theory" , Springer (1989)
[a2]	J. Dassow, Gh. Păun, A. Salomaa, "Regulated rewriting" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , Springer (1997)
[a3]	D. Rosenkrantz, "Programmed grammars and classes of formal languages" J. ACM , 16 (1969) pp. 107 –131