Clover ash and positive shell

The clover ash shell (also finite conclusion , Kleene - * - Final , concatenation envelope or stellar envelope called) of an alphabet or a formal language is the amount of all the words that by any concatenation (linking) of symbols of the alphabet and words of the language are formed can, including the empty word . It is named after the American mathematician and logician Stephen Cole Kleene . In contrast, the positive envelope (also called Kleene - + - closure ) of an alphabet or a formal language is the set of all words that can be formed from the symbols of or from words of and that only contains the empty word if the positive envelope is applied to a language which itself contains the empty word as an element. ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle \varepsilon }$ ${\displaystyle \Sigma }$ ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle L}$

The operator of the Kleene shell is the Kleene star " ". Thus, the representation of the clover eschen shell is an alphabet equal and a language equal . In contrast, the operator of the positive envelope is the plus sign " ", so that the positive envelope of an alphabet is represented with and a language with . ${\displaystyle ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle L}$ ${\displaystyle L^{*}}$ ${\displaystyle ^{+}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{+}}$ ${\displaystyle L}$ ${\displaystyle L^{+}}$

Based on the Kleene - * operator in languages, the * operator in regular expressions is also called the Kleene - * operator. The number of nested Kleene - * operators determines the star height of a regular expression.

definition

Shell operator for alphabets

The clover's shell of an alphabet is a language that contains all the words above the alphabet. It can be defined with the help of structural induction . In the induction beginning, one first defines that the empty word is contained in the Kleene envelope, and in the induction step it is defined that for each word that is an element of the Kleene envelope, the concatenations for all symbols are also elements of the Kleene envelope: ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon }$ ${\displaystyle w}$ ${\displaystyle w\circ a}$ ${\displaystyle a\in \Sigma }$

• Induction start: ${\displaystyle \varepsilon \in \Sigma ^{*}}$
• Induction step: ${\displaystyle (w\in \Sigma ^{*})\land (a\in \Sigma )\Rightarrow w\circ a\in \Sigma ^{*}}$

The positive envelope of an alphabet is defined as the Kleenian envelope of this alphabet without the empty word: ${\displaystyle \Sigma ^{+}}$ ${\displaystyle \Sigma }$

${\displaystyle \Sigma ^{+}:=\Sigma ^{*}\setminus \{\varepsilon \}}$

Starting from the Kleen's shell, subsets of the words with fixed length can be defined. ${\displaystyle n}$

${\displaystyle \Sigma ^{n}:=\{w\mid w\in \Sigma ^{*}\land \left|w\right|=n\}}$

Alternatively, it can be defined as the -fold Cartesian product of the alphabet, i.e. ${\displaystyle \Sigma ^{n}}$ ${\displaystyle n}$

${\displaystyle \Sigma ^{n}=\prod _{i=1}^{n}\Sigma =\underbrace {\Sigma \times \dotsb \times \Sigma } _{n{\text{-mal}}}}$with . ${\displaystyle \Sigma ^{0}=\{\varepsilon \}}$

Then:

${\displaystyle \Sigma ^{*}=\bigcup _{i\in \mathbb {N} _{0}}\Sigma ^{i}}$ and

${\displaystyle \Sigma ^{+}=\bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$

Shell operator for languages

The Kleenian shell of a language is the union of all its power languages (repeated concatenation of languages): ${\displaystyle L^{*}}$ ${\displaystyle L}$

${\displaystyle L^{*}:=\bigcup _{i\in \mathbb {N} _{0}}L^{i}}$

Where and . ${\displaystyle L^{0}=\{\varepsilon \}}$ ${\displaystyle L^{n+1}=L^{n}\circ L}$

The positive envelope of a language is defined similarly, it is the union of all powers greater than or equal to 1: ${\displaystyle L^{+}}$ ${\displaystyle L}$ ${\displaystyle L}$

${\displaystyle L^{+}:=\bigcup _{i\in \mathbb {N} }L^{i}}$

Examples

Alphabets

The clover's shell of the alphabet contains the empty word , the word and therefore the word and so on. So is ${\displaystyle \Sigma =\{a\}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon \circ a=a}$ ${\displaystyle a\circ a=aa}$

${\displaystyle \Sigma ^{*}=\{\varepsilon ,a,aa,\dotsc \}}$.

For the alphabet is true , and so on. So is ${\displaystyle \Sigma =\{a,b\}}$ ${\displaystyle \Sigma ^{2}=\{aa,ab,ba,bb\}}$ ${\displaystyle \Sigma ^{3}=\{aaa,aab,aba,abb,baa,bab,bba,bbb\}}$

${\displaystyle \Sigma ^{*}=\{\varepsilon ,a,b,aa,ab,ba,bb,aaa,aab,aba,\dotsc \}}$.

languages

The Kleenian shell of language is the set of all words that are made up of and , as well as the empty word: ${\displaystyle L=\{aa,bb\}}$ ${\displaystyle aa}$ ${\displaystyle bb}$

${\displaystyle L^{*}=\{\varepsilon ,aa,bb,aaaa,aabb,bbbb,bbaa,bbaabb,aabbaa,\dotsc \}}$

The positive envelope is accordingly:

${\displaystyle L^{+}=\{aa,bb,aaaa,aabb,bbbb,bbaa,bbaabb,aabbaa,\dotsc \}}$

The Kleenian shell of the empty language and the language of the empty word contains only the empty word:

${\displaystyle \{\}^{*}=\{\varepsilon \}^{*}=\{\varepsilon \}}$

The positive envelope of the empty language is empty, that of the language of the empty word contains only the empty word:

${\displaystyle \{\}^{+}=\{\}}$

${\displaystyle \{\varepsilon \}^{+}=\{\varepsilon \}}$

features

• The Kleene envelope and the positive envelope (if the latter contains the empty word) are each the carrier set of the monoid with the concatenation of words as the operator and the empty word as the neutral element . So the Kleen's shell forms the free monoid over an alphabet. The Kleenesche shell as well as the positive shell are thus also closed against the concatenation. ${\displaystyle \varepsilon }$

• The Kleenesche and the positive envelope are countably infinite for all languages ​​that contain at least one non-empty word :

${\displaystyle L\notin \{\{\},\{\varepsilon \}\}\Rightarrow |L^{*}|=|\mathbb {N} |}$

${\displaystyle L\notin \{\{\},\{\varepsilon \}\}\Rightarrow |L^{+}|=|\mathbb {N} |}$

• If a language contains the empty word, the Kleenesche and the positive envelope of are identical; the reverse is also true: ${\displaystyle L}$ ${\displaystyle L}$

${\displaystyle \varepsilon \in L\Leftrightarrow L^{*}=L^{+}}$

Generalizations

The countably infinite sequences of characters from the alphabet are denoted by, see: = . denotes the entire set of finite sequences and infinite sequences of characters  . ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \aleph _{0}}$
${\displaystyle \Sigma ^{\infty }}$ ${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$ ${\displaystyle \Sigma }$

literature

• John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory. 3rd corrected edition. Addison-Wesley, Bonn et al. 1994, ISBN 3-89319-744-3 .
• Katrin Erk, Lutz Priese: Theoretical Computer Science. A comprehensive introduction . 2nd expanded edition. Springer-Verlag, Berlin et al. 2002, ISBN 3-540-42624-8 , pp. 27-29 .