DERIVATIVES OF REGULAR EXPRESSIONS
DERIVATIVES OF REGULAR EXPRESSIONS
复制标题
DOI：
10.1145/321239.321249
复制
发表时间：
1964-01-01
影响因子：
2.5
通讯作者：
BRZOZOWSKI, JA
中科院分区：
文献类型：
--
作者：
BRZOZOWSKI, JA
Kleene的正则表达式，可用于描述时序电路，定义使用三个操作符（联合，级联和重复）的序列集。如果正则表达式语言通过包含其他逻辑操作而得到丰富，那么问题的文字描述可以更容易地放在正则表达式语言中。然而，在将正则表达式描述转换为状态图的问题中，现有方法要么不能处理具有附加运算符的表达式，要么由于存在这样的运算符而变得相当复杂。本文引入了正则表达式导数的概念，并讨论了导数的性质。这以一种非常自然的方式导致从包含任意数量逻辑运算符的正则表达式构造状态图。
Kleene's regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate) on sets of sequences. Word descriptions of problems can be more easily put in the regular expression language if the language is enriched by the inclusion of other logical operations. However, il~ the problem of converting the regular expression description to a state diagram, the existing methods either cannot handle expressions with additional operators, or are made quite complicated by the presence of such operators. In this paper the notion of a derivative of a regular expression is introduced atld the properties of derivatives are discussed. This leads, in a very natural way, to the construction of a state diagram from a regular expression containing any number of logical operators.