Kleene star | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid construction. The application of the Kleene star to a set is written as . It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterize certain automata, where it means "zero or more repetitions". If is a set of strings, then is defined as the smallest superset of that contains the empty string and is closed under the string concatenation operation. If is a set of symbols or characters, then is the set of all strings over symbols in , including the empty string . The set can also be described as the set containing the empty string and all finite-length strings that can be generated by concatenating arbitrary elements of , allowing the use of the same element multiple times. If is either the empty set ∅ or the singleton set , then ; if is any other finite set or countably infinite set, then is a countably infinite set. As a consequence, each formal language over a finite or countably infinite alphabet is countable, since it is a subset of the countably infinite set . The operators are used in rewrite rules for generative grammars. Given a set , define (the language consisting only of the empty string), and define recursively the set for each . If is a formal language, then , the -th power of the set , is a shorthand for the concatenation of set with itself times. That is, can be understood to be the set of all strings that can be represented as the concatenation of strings in . The definition of Kleene star on is This means that the Kleene star operator is an idempotent unary operator: for any set of strings or characters, as for every . In some formal language studies, (e.g. AFL theory) a variation on the Kleene star operation called the Kleene plus is used. The Kleene plus omits the term in the above union.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (18)

Related courses (2)

Related lectures (32)

Monoid

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids are semigroups with identity. Such algebraic structures occur in several branches of mathematics. The functions from a set into itself form a monoid with respect to function composition. More generally, in , the morphisms of an to itself form a monoid, and, conversely, a monoid may be viewed as a category with a single object.

Free monoid

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures.

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Regular Expressions and Lexer Idea CS-320: Computer language processing

Covers regular expressions, Kleene's contributions, logic, lexical analysis, and manual lexer construction.

Introduction to C++ Strings MOOC: Introduction to Programming in C++

Covers the basics of working with strings in C++, including declaration, initialization, characters, assignment, concatenation, and comparison.

Recursive Algorithms: Induction & Sorting CS-101: Advanced information, computation, communication I

Covers induction, recursion, sorting algorithms, and the merge sort complexity in computer science.