Kleene Closing . In Linguistics , Mathematics and Informatics and in the Theory of Formal Languages it refers to the unitary operation of languages that identifies the successive concatenation of any or more times of each and every one of the strings that make up the language in question.
Summary
[ hide ]
- 1 Definitions
- 2 Examples
- 3 Consequences
- 4 See also
- 5 Sources
Definitions
Let the formal languages A and B be the concatenated product, denoted AxB is defined by AxB , the set of all strings ab where a is each string of A and b all strings of B , that is .
Let the formal language L be defined to the nth concatenated power operation of L and denoted L n ‘ according to the definitions:
- L 0= {ε} .
- L 1= L .
- L 2= lxl = {a 1 to 1 , to 1 to 2 } for all strings to i and a j of L .
- L n= LxL n-1 . (Recursive definition).
Let it be a formal language L = {a, b, c, …} , the operation on the language L is called Kleene’s closure and the union of languages is denoted L * .
There is also the positive Kleene closure which is denoted L + = L * -L 0 .
Examples
- Let the language be L = {a}, L * = {ε, a, aa, aaa, aaaa, …} .
- Let B = {0,1}formal language, B * = {ε, 0,1,00,01,10,11,000,001,010,011, …} .
- Let the regular expression e 1* be the equivalent AF take the form: where T (e 1 ) is the AFND-V resulting from the expressions e 1
Consequences
The closure of Kleene is of great importance in the theory of formal languages and their basic operations, since it allows us to represent languages obtained from recurring concatenations and other formalisms of great use in all types of languages of the Chomsky hierarchy .
For example, in regular languages the representation of simpler versions such as the classings in regular expressions is common , allowing a close interrelation between the different types of forms of recognition and representation of regular languages, in finite automata and regular grammars .
Similar occurs in LLC reductions such as LL (k) and LR (k) .

