请输入您要查询的字词:

 

单词 GeneralizedRegularExpression
释义

generalized regular expression


Recall that a regular expressionMathworldPlanetmath over an alphabet Σ is a finite strings of symbols that are elements of Σ, together with symbols , , , *, as well as ( and ), which is put together based on a set of expression formation rules. In a generalized regular expression, additional symbols and ¬ are tossed in also. Formally,

Definition. Given an alphabet Σ, let S be the set {,,,*,,¬,(,)}, considered to be disjoint from Σ. Let X be the smallest subset of (ΣS)* containing the following:

  • any regular expression is in X,

  • if u,vY, then (uv),(¬u)X.

An element of X is called a generalized regular expression over Σ.

Like regular expressions, every generalized regular expressions are designed to represent languagesPlanetmathPlanetmath (it is clear that and ¬ are intended to mean set-theoretic intersectionDlmfMathworldPlanetmath and complementation). If u is a generalized regular expression:

  • if u is regular expression, then the language represented by u as a generalized regular expression is L(u), the language represented by u as a regular expression;

  • if A is represented by u and B is represented by v, then AB is represented by (uv)

  • if A is represented by u, then Σ*-A is represented by (¬u).

By inductionMathworldPlanetmath, it is easy to see that, given a generalized regular expression u, there is exactly one language represented by u. We denote L(u) the language represented by u, and 𝒢 the family of languages represented by generalized regular expressions.

Since regular languages are closed under intersection and complementation, generalized regular expressions in this regard are no powerful than regular expressions. The symbols ¬ and are therefore extraneous. In other words,

=𝒢,

where is the family of regular languages.

References

  • 1 A. Salomaa, Formal LanguagesMathworldPlanetmath, Academic Press, New York (1973).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 9:51:27