Structuring grammar systems by priorities and hierarchies
A grammar system is a finite set of grammars that cooperate to generate a language. We consider two generalizations of grammar systems: (l) adding a priority relation between single grammar components, and (2) considering hierarchical components which by themselves are grammar systems. The generativ...
Saved in:
| Main Authors: | |
|---|---|
| Format: | Article |
| Published: |
1994
|
| Series: | Acta cybernetica
11 No. 3 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12528 |
| Summary: | A grammar system is a finite set of grammars that cooperate to generate a language. We consider two generalizations of grammar systems: (l) adding a priority relation between single grammar components, and (2) considering hierarchical components which by themselves are grammar systems. The generative power of these generalized grammar systems is investigated, and compared with the generative power of ordinary grammar systems and of some well-known types of grammars with regulated rewriting (such as matrix grammars). We prove that for many cooperating strategies the use of priority relation increases the generative capacity, however this is not the case for the maximal mode of derivation (an important case, because it gives a characterization of the ETOL languages). We also demonstrate that in many cases the use of hierarchical components does not increase the generative power. |
|---|---|
| Physical Description: | 189-204 |
| ISSN: | 0324-721X |