Kleene algebra

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

for all $a,b,c\in A$.

For a given alphabet $\mathrm{\Sigma }$, the set of all languages over $\mathrm{\Sigma }$, as well as the set of all regular languages over $\mathrm{\Sigma }$, are examples of Kleene algebras. Similarly, sets of regular expressions (regular sets) over $\mathrm{\Sigma }$ are a form (or close variant) of a Kleene algebra: let $A$ be the set of all regular sets over a set $\mathrm{\Sigma }$ of alphabets. Then $A$ is a Kleene algebra if we identify $\mathrm{\varnothing }$ as $0$, the singleton containing the empty string $\lambda$ as $1$, concatenation operation as $\cdot$, the union operation as $+$, and the Kleene star operation as ${}^{*}$. For example, let $a$ be a set of regular expression, then

$$a^{*}=\{\lambda \}\cup a\cup a^2\cup \mathrm{\cdots }\cup a^n\cup \mathrm{\cdots },$$

so that

$$a{a}^{*}=a\cup a^2\cup \mathrm{\cdots }\cup a^n\cup \mathrm{\cdots }.$$

Adding $1$ on both sides and we have

$$1+a{a}^{*}=\{\lambda \}\cup a{a}^{*}=\{\lambda \}\cup a\cup a^2\cup \mathrm{\cdots }\cup a^n\cup \mathrm{\cdots }=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).

Title	Kleene algebra
Canonical name	KleeneAlgebra
Date of creation	2013-03-22 12:27:51
Last modified on	2013-03-22 12:27:51
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	10
Author	CWoo (3771)
Entry type	Definition
Classification	msc 20M35
Classification	msc 68Q70
Related topic	KleeneStar
Related topic	Semiring
Related topic	RegularExpression
Related topic	RegularLanguage
Related topic	KleeneAlgebra2