Kleene Closure

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 n ‘ according to the definitions:

  • 0= {ε} .
  • 1= L .
  • 2= lxl = {a 1 to 1 , to 1 to 2 } for all strings to i and j of 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 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 1* be the equivalent AF take the form: where T (e 1 ) is the AFND-V resulting from the expressions 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) .

 

Leave a Comment