Regulated Rewriting in Formal Language Theory
Regulated Rewriting in Formal Language Theory
复制标题
DOI：
10.1007/978-3-642-74932-2
复制
发表时间：
1989
期刊：
影响因子：
64.5
通讯作者：
J. Dassow;G. Paun
中科院分区：
文献类型：
--
作者：
J. Dassow;G. Paun
形式语言理论诞生于本世纪中叶，作为建模和研究自然语言语法的工具，它主要是与编程语言处理相关地发展起来的。当然，我们不能否认神经元网络研究、逻辑学以及早期研究的数学动机的推动。该理论已迅速成为一个成熟的，具体的问题，技术和结果，并与内部自我激励的生活。形式语言理论足够抽象，可以处理模拟现象的本质，在过去几年中，形式语言理论已被应用于许多进一步的非语言学领域，有时令人惊讶地远离以前的应用领域;这些领域是发育生物学、经济模型、民俗符号学、戏剧和音乐作品、密码学、社会学、心理学，所有这些应用以及传统的自然语言和程序设计语言的应用都揭示了一个相当普遍的结论：上下文无关文法，最发达和最”易处理”的Chomsky文法，往往是不够的。“世界是非上下文无关的”（我们将在0.4节”证明”这一陈述）。另一方面，上下文相关文法过于强大，而且绝对是”棘手的”（许多问题是不可判定的或仍然是开放的;没有对非终结符的语义解释等等）。这就是寻找中间生成设备的原因，将上下文无关语法的简单和美丽与上下文相关语法的功能结合起来。因此，引入了限制派生的语法，即以非上下文无关的方式使用上下文无关核心规则的语法。第一类文法是ABRAHAM在1965年定义的矩阵文法。它们的规则按序列（“矩阵”）分组，推导的一个步骤包括逐个使用矩阵的所有规则。在此期间，大约有25种不同的限制被定义（其中一些有许多变体）。我们引用其中最著名的：编程，随机上下文，索引，分散上下文和并行语法。形式语言理论的一个强有力的分支就这样出现了，这个分支至今还没有总结性的专著。本书旨在填补这一空白。
The formal language theory was born in the middle of our century as a tool for modelling and investigating the syntax of natural languages, and it has been developed mainly in connection with programming language handling. Of course, one cannot deny the impulses from neuronal net investigations, from logic, as well as the mathematical motivation of the early researches. The theory has rapidly become a mature one, with specific problems, techniques and results and with an internal self-motivated life. Abstract enough to deal with the essence of modelled phenomena, formal language theory has been applied during the last years to many further non-linguistical fields, sometimes surprisingly far from the previous areas of applications; such fields are developmental biology, economic modelling, semiotics of folklore, dramatic and musical works, cryptography, sociology, psychology, and so on.All these applications as well as the traditional ones to natural and programming languages revealed a rather common conclusion: very frequently, context-free grammars, the most developed and the most" tractable" type of Chomsky grammars, are not sufficient." The world is non-context-free"(and we shall" prove" this statement in Section 0.4). On the other hand, the context-sensitive grammars are too powerful and definitely" intractable"(many problems are undecidable or are still open; there is no semantic interpretation of the nonterminals and so on). This is the reason to look for intermediate generative devices, conjoining the simplicity and the beauty of context-free grammars with the power of context-sensitive ones. Therefore, grammars with restrictions in derivations have been introduced, ie grammars with context-free core rules used in a non-context-free manner. The first type of such grammars were the matrix grammars defined by ABRAHAM in 1965. Their rules are grouped in sequences (" matrices"), and a step of a derivation consists in using, one by one, all rules of a matrix. About twenty five further different restrictions have been defined in the meantime (some with many variants). We quote the most well known of them: programmed, random context, indexed, scattered context, and parallel grammars. A powerful branch of formal language theory has been appeared in this way, a branch which so far has no summarizing monographs. The present book aims to fill this gap.