Namespaces
Variants
Actions

Difference between revisions of "Regulated rewriting"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
r1100601.png
 +
$#A+1 = 46 n = 0
 +
$#C+1 = 46 : ~/encyclopedia/old_files/data/R110/R.1100060 Regulated rewriting
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
An important branch of [[Formal language|formal language]] theory, starting from the observation that most natural and artificial languages of interest are non-context-free (cf. [[Grammar, context-free|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.
 
An important branch of [[Formal language|formal language]] theory, starting from the observation that most natural and artificial languages of interest are non-context-free (cf. [[Grammar, context-free|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.
  
Line 6: Line 18:
 
A programmed grammar (introduced in [[#References|[a3]]]) is a construct
 
A programmed grammar (introduced in [[#References|[a3]]]) is a construct
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100601.png" /></td> </tr></table>
+
$$
 +
G = ( N,T,S,P ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100602.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100603.png" /> are disjoint alphabets (the non-terminal and the terminal alphabet), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100604.png" /> (axiom), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100605.png" /> is a finite set of quadruples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100606.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100607.png" /> is a context-free rule over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100608.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r1100609.png" /> is the label of the rule, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006011.png" /> are sets of labels of rules in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006012.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006013.png" /> is the success field and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006014.png" /> is the failure field). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006015.png" /> be the set of all labels of rules in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006016.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006017.png" /> one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006018.png" /> if one of the following two cases holds:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006020.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006022.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006023.png" />;
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006024.png" /> does not contain the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006025.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006028.png" />. (Note the way of controlling the sequencing of rules application by means of the mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006030.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006031.png" /> to the power set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006032.png" />.) The language generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006033.png" /> is
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006034.png" /></td> </tr></table>
+
$$
 +
L ( G ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006035.png" /></td> </tr></table>
+
$$
 +
=  
 +
\left \{ {w \in T  ^ {*} } : {( r,S ) \Rightarrow  ^ {*} ( r  ^  \prime  ,w )  \textrm{ for  some  }  r,r ^  \prime  \in { \mathop{\rm Lab} } } \right \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006036.png" /> is the reflexive and transitive closure of the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006037.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006038.png" /> be the family of languages of this form; when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006039.png" />-rules are not allowed, one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006040.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006041.png" /> for all rules in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006042.png" />, one says that the grammar is without appearance checking; the corresponding families of languages are denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006043.png" />, PR. Denote by CF, CS, and RE the families of context-free, context-sensitive, and recursively enumerable languages, respectively. Then:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006045.png" />;
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110060/r11006046.png" /> is an [[Abstract family of languages|abstract family of languages]] (cf. also [[Trio|Trio]]).
+
2) $  { \mathop{\rm PR} } _ {\textrm{ ac  }  } $
 +
is an [[Abstract family of languages|abstract family of languages]] (cf. also [[Trio|Trio]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Dassow,  Gh. Păun,  "Regulated rewriting in formal language theory" , Springer  (1989)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Dassow,  Gh. Păun,  A. Salomaa,  "Regulated rewriting"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Handbook of Formal Languages'' , Springer  (1997)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D. Rosenkrantz,  "Programmed grammars and classes of formal languages"  ''J. ACM'' , '''16'''  (1969)  pp. 107 –131</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Dassow,  Gh. Păun,  "Regulated rewriting in formal language theory" , Springer  (1989)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Dassow,  Gh. Păun,  A. Salomaa,  "Regulated rewriting"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Handbook of Formal Languages'' , Springer  (1997)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D. Rosenkrantz,  "Programmed grammars and classes of formal languages"  ''J. ACM'' , '''16'''  (1969)  pp. 107 –131</TD></TR></table>

Latest revision as of 08:10, 6 June 2020


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
How to Cite This Entry:
Regulated rewriting. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Regulated_rewriting&oldid=48492
This article was adapted from an original article by Gh. Păun (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article