##
**Grammars with context conditions and their applications.**
*(English)*
Zbl 1087.68045

Hoboken, NJ: John Wiley & Sons (ISBN 0-471-71831-9/hbk; 978-0-471-73656-1/ebook). ix, 216 p. (2005).

The study of grammars with context conditions is an important area of formal language theory. Up to now results in this area have been scattered in various journal papers. It is the aim of this book, to systematically summarize the concepts and results of this field.

In chapter 2 an introduction to formal languages and grammars is given.

In chapter 3 context conditions placed on derivation domains are treated: A wm-grammar is a pair \((G, W)\) where \(G = (V, T, P, S)\) is a context-free grammar (with terminals \(T\), nonterminals \(V-T\), \(S\in V-T\), and rule set \(P\)) and \(W\) a finite language over \(V\). \((G, W)\) is of degree \(i\) (a natural number), if \(y\in W\) implies \(|y| \leq i\). The direct derivation \(\Rightarrow_{(G,W)}\) on \(W^*\) is defined as follows: If \(A\to y\in P\), \(xAz\), \(xyz\in W^*\), then \(x Az\Rightarrow^*_{G,W)} xyz\). Of course \(L(G,W) = \{w\in T^*: S\Rightarrow^*_{(G,W)} w\}\). \((G, W)\) is called propagating, if \(A\to y\in P\) implies \(y\neq\varepsilon\). Let WM\((i)\) and prop-WM\((i)\) be the families of languages generated by wm-grammars of degree \(i\) and by propagating wm-grammars of degree \(i\) respectively. The main results proved are: prop-WM(2) is the family of context-sensitive languages; WM(2) is the family of recursively enumerable languages. Additionally, parallel wm-grammars are studied. The concept is similar to wm-grammars, but \(G\) has to be an E0L grammar. Similar results are proved.

In chapter 4 grammars with context conditions placed on the use of productions are studied. To give a typical result, let first, for \(u\in V^*\) and \(U\subseteq V^*\), \(|U| < \infty\), \(\text{sub}(u)\) be the set of all substrings of \(u\) and \(\max(U)\) be the length of the longest word in \(U\), respectively. A context-conditional grammar is a quadruple \(G= (V, T, P, S)\), where \(V, T, S\) are defined as above, and \(P\) is a finite set of productions of the form \((A\to x\), Per, For), \(A\to x\) as above and Per, For \(\subseteq V^+\). \(G\) has degree \((r,s)\) if, for every \((A\to x,\text{Per,\,For})\in P\), \(\max(\text{Per})\leq r\) and \(\max(\text{For}) \leq s\). \(G\) is called propagating, if \((A\to x,\text{Per,\,For})\in P\) implies \(x\neq \varepsilon\). The direct derivation \(\Rightarrow_G\) on \(V^*\) is defined as follows: \(u\Rightarrow_G v\), if there are \(u_1,u_2\in V^*\), \((A \to x,\text{Per,\,For})\in P\), such that \(u = u_1Au_2\), \(v = u_1xu_2\), \(\text{Per}\subseteq \text{sub}(u)\), and \(\text{For}\cap \text{sub}(u) =\emptyset\). The families of languages generated by context-conditional grammars and propagating context-conditional grammars of degree \((r,s)\) are denoted by CG\((r,s)\) and \(\text{prop-CG}(r,s)\) respectively. Let \[ \text{CG}= \bigcup_{r,s\geq 0}\text{CG}(r,s),\quad\text{prop-CG}= \bigcup_{r,s\geq 0}\text{prop-CG}(r,s). \] It is proved that prop-CG is the family of context-sensitive languages and CG is the family of recursively enumerable languages. Similar results are proved for special cases of context-conditional grammars. Again, also parallel context-conditional grammars are studied.

Chapter 5 deals with a third type of context conditions: context conditions placed on the neighbourhood of rewritten symbols, including classical context-dependent grammars but also scattered context grammars in which rewriting depends on symbols scattered throughout the word to be rewritten. Again both sequential and parallel grammars are studied.

Chapter 6 studies grammatical transformations of grammars with context conditions to some other equivalent grammars so that both the input grammar and the transformed grammars generate their languages in a very similar way.

Chapter 7 demonstrates the use of grammars with context-conditions by several applications related to biology.

The monograph reflects the state of the art in grammars with context conditions.

In chapter 2 an introduction to formal languages and grammars is given.

In chapter 3 context conditions placed on derivation domains are treated: A wm-grammar is a pair \((G, W)\) where \(G = (V, T, P, S)\) is a context-free grammar (with terminals \(T\), nonterminals \(V-T\), \(S\in V-T\), and rule set \(P\)) and \(W\) a finite language over \(V\). \((G, W)\) is of degree \(i\) (a natural number), if \(y\in W\) implies \(|y| \leq i\). The direct derivation \(\Rightarrow_{(G,W)}\) on \(W^*\) is defined as follows: If \(A\to y\in P\), \(xAz\), \(xyz\in W^*\), then \(x Az\Rightarrow^*_{G,W)} xyz\). Of course \(L(G,W) = \{w\in T^*: S\Rightarrow^*_{(G,W)} w\}\). \((G, W)\) is called propagating, if \(A\to y\in P\) implies \(y\neq\varepsilon\). Let WM\((i)\) and prop-WM\((i)\) be the families of languages generated by wm-grammars of degree \(i\) and by propagating wm-grammars of degree \(i\) respectively. The main results proved are: prop-WM(2) is the family of context-sensitive languages; WM(2) is the family of recursively enumerable languages. Additionally, parallel wm-grammars are studied. The concept is similar to wm-grammars, but \(G\) has to be an E0L grammar. Similar results are proved.

In chapter 4 grammars with context conditions placed on the use of productions are studied. To give a typical result, let first, for \(u\in V^*\) and \(U\subseteq V^*\), \(|U| < \infty\), \(\text{sub}(u)\) be the set of all substrings of \(u\) and \(\max(U)\) be the length of the longest word in \(U\), respectively. A context-conditional grammar is a quadruple \(G= (V, T, P, S)\), where \(V, T, S\) are defined as above, and \(P\) is a finite set of productions of the form \((A\to x\), Per, For), \(A\to x\) as above and Per, For \(\subseteq V^+\). \(G\) has degree \((r,s)\) if, for every \((A\to x,\text{Per,\,For})\in P\), \(\max(\text{Per})\leq r\) and \(\max(\text{For}) \leq s\). \(G\) is called propagating, if \((A\to x,\text{Per,\,For})\in P\) implies \(x\neq \varepsilon\). The direct derivation \(\Rightarrow_G\) on \(V^*\) is defined as follows: \(u\Rightarrow_G v\), if there are \(u_1,u_2\in V^*\), \((A \to x,\text{Per,\,For})\in P\), such that \(u = u_1Au_2\), \(v = u_1xu_2\), \(\text{Per}\subseteq \text{sub}(u)\), and \(\text{For}\cap \text{sub}(u) =\emptyset\). The families of languages generated by context-conditional grammars and propagating context-conditional grammars of degree \((r,s)\) are denoted by CG\((r,s)\) and \(\text{prop-CG}(r,s)\) respectively. Let \[ \text{CG}= \bigcup_{r,s\geq 0}\text{CG}(r,s),\quad\text{prop-CG}= \bigcup_{r,s\geq 0}\text{prop-CG}(r,s). \] It is proved that prop-CG is the family of context-sensitive languages and CG is the family of recursively enumerable languages. Similar results are proved for special cases of context-conditional grammars. Again, also parallel context-conditional grammars are studied.

Chapter 5 deals with a third type of context conditions: context conditions placed on the neighbourhood of rewritten symbols, including classical context-dependent grammars but also scattered context grammars in which rewriting depends on symbols scattered throughout the word to be rewritten. Again both sequential and parallel grammars are studied.

Chapter 6 studies grammatical transformations of grammars with context conditions to some other equivalent grammars so that both the input grammar and the transformed grammars generate their languages in a very similar way.

Chapter 7 demonstrates the use of grammars with context-conditions by several applications related to biology.

The monograph reflects the state of the art in grammars with context conditions.

Reviewer: A. Widiger (Rostock)