请输入您要查询的字词:

 

单词 KleeneAlgebra
释义

Kleene algebra


A Kleene algebra (A,,+,*,0,1) is an idempotent semiring(A,,+,0,1) with an additional (right-associative) unary operator *, called the Kleene star, which satisfies

1+aa*a*,ac+bca*bc,1+a*aa*,ca+bcba*c,

for all a,b,cA.

For a given alphabet Σ, the set of all languagesPlanetmathPlanetmath over Σ, as well as the set of all regular languages over Σ, are examples of Kleene algebras. Similarly, sets of regular expressionsMathworldPlanetmath (regular sets) over Σ are a form (or close variant) of a Kleene algebra: let A be the set of all regular sets over a set Σ of alphabets. Then A is a Kleene algebra if we identify as 0, the singleton containing the empty string λ as 1, concatenationMathworldPlanetmath operationMathworldPlanetmath as , the union operation as +, and the Kleene star operation as *. For example, let a be a set of regular expression, then

a*={λ}aa2an,

so that

aa*=aa2an.

Adding 1 on both sides and we have

1+aa*={λ}aa*={λ}aa2an=a*.

The other conditions are checked similarly.

Remark. There is another notion of a Kleene algebra, which arises from lattices. For more detail, see here (http://planetmath.org/KleeneAlgebra2).

TitleKleene algebra
Canonical nameKleeneAlgebra
Date of creation2013-03-22 12:27:51
Last modified on2013-03-22 12:27:51
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id10
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 20M35
Classificationmsc 68Q70
Related topicKleeneStar
Related topicSemiringMathworldPlanetmath
Related topicRegularExpression
Related topicRegularLanguage
Related topicKleeneAlgebra2
随便看

 

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

 

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