Editing Kleene algebra (section)

== Examples ==

{| class="wikitable" style="float:right"
|+ Notational correspondence between 
|-
! [[#Definition|Kleene algebras]] and 
| + || · || <sup>*</sup> || 0 || 1
|-
! [[Regular expression#Formal language theory|Regular expressions]] 
| | | || not written  || <sup>*</sup> || ∅  || ε
|}
Let Σ be a finite set (an "alphabet") and let ''A'' be the set of all [[Regular expression#Formal language theory|regular expression]]s over Σ. We consider two such regular expressions equal if they describe the same [[formal language|language]]. Then ''A'' forms a Kleene algebra. In fact, this is a [[free object|free]] Kleene algebra in the sense that any equation among regular expressions follows from the Kleene algebra axioms and is therefore valid in every Kleene algebra.

Again let Σ be an alphabet. Let ''A'' be the set of all [[regular language]]s over Σ (or the set of all [[context-free language]]s over Σ; or the set of all [[recursive language]]s over Σ; or the set of ''all'' languages over Σ). Then the [[union (set theory)|union]] (written as +) and the [[concatenation#Concatenation of sets of strings|concatenation]] (written as ·) of two elements of ''A'' again belong to ''A'', and so does the [[Kleene star]] operation applied to any element of ''A''. We obtain a Kleene algebra ''A'' with 0 being the [[empty set]] and 1 being the set that only contains the [[empty string]].

Let ''M'' be a [[monoid]] with identity element ''e'' and let ''A'' be the set of all [[subset]]s of ''M''. For two such subsets ''S'' and ''T'', let ''S'' + ''T'' be the union of ''S'' and ''T'' and set ''ST'' = {''st'' : ''s'' in ''S'' and ''t'' in ''T''}. ''S''<sup>*</sup> is defined as the submonoid of ''M'' generated by ''S'', which can be described as {''e''} ∪ ''S'' ∪ ''SS'' ∪ ''SSS'' ∪ ... Then ''A'' forms a Kleene algebra with 0 being the empty set and 1 being {''e''}. An analogous construction can be performed for any small [[category theory|category]].

The [[linear subspace]]s of a unital [[algebra over a field]] form a Kleene algebra.  Given linear subspaces ''V'' and ''W'', define ''V'' + ''W'' to be the sum of the two subspaces, and 0 to be the trivial subspace {0}.  Define {{math|1=''V'' · ''W'' = span {{mset|v · w | v ∈ V, w ∈ W}}}}, the [[linear span]] of the product of vectors from ''V'' and ''W'' respectively.  Define {{math|1=1 = span {I}<nowiki/>}}, the span of the unit of the algebra.  The closure of ''V'' is the [[direct sum of modules|direct sum]] of all powers of ''V''.

<math display="block">V^{*} = \bigoplus_{i = 0}^{\infty} V^{i}</math>

Suppose ''M'' is a set and ''A'' is the set of all [[binary relation]]s on ''M''. Taking + to be the union, · to be the composition and <sup>*</sup> to be the [[reflexive transitive closure]], we obtain a Kleene algebra.

Every [[Boolean algebra (structure)|Boolean algebra]] with operations <math>\lor</math> and <math>\land</math> turns into a Kleene algebra if we use <math>\lor</math> for +, <math>\land</math> for · and set ''a''<sup>*</sup> = 1 for all ''a''.

A quite different Kleene algebra can be used to implement the [[Floyd–Warshall algorithm]], computing the [[shortest path problem|shortest path's length]] for every two vertices  of a [[graph theory|weighted directed graph]], by [[Kleene's algorithm]], computing a regular expression for every two states of a [[deterministic finite automaton]].
Using the [[extended real number line]], take ''a'' + ''b'' to be the minimum of ''a'' and ''b'' and ''ab'' to be the ordinary sum of ''a'' and ''b'' (with the sum of +∞ and −∞ being defined as +∞). ''a''<sup>*</sup> is defined to be the real number zero for nonnegative ''a'' and −∞ for negative ''a''. This is a Kleene algebra with zero element +∞ and one element the real number zero. 
A weighted directed graph can then be considered as a deterministic finite automaton, with each transition labelled by its weight.
For any two graph nodes (automaton states), the regular expressions computed from Kleene's algorithm evaluates, in this particular Kleene algebra, to the shortest path length between the nodes.<ref>{{citation|title=Handbook of Graph Theory| series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press| year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref>