A regular expression is built from alphabet symbols, the empty language and the empty word using finite union, concatenation and Kleene star.
The Kleene star of a language consists of every finite concatenation of words from , including the empty concatenation.
The positive closure of a formal language is the language of all concatenations of one or more words from :
Here is -fold concatenation of formal languages, while the Kleene star also permits , whose contribution is the empty word . Thus .
For , positive closure is . If , then as well: positive counts chosen words, not their total character length. For the empty language, but . This operation preserves regular languages and is one of the closure requirements in an abstract family of languages.
This theorem characterizes a regular language by regular expressions and acceptance by a finite-state automaton. Kleene's theorem states that a language is denoted by a regular expression exactly when it is accepted by a finite automaton.

Ancestors (5)

  1. Formal language theory
  2. Foundations of mathematics
  3. Area of mathematics
  4. Mathematics
  5. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (2)

A regular expression (regex or regexp) is a sequence of characters that defines a search pattern. It is primarily used for string matching and manipulation tasks in various programming languages and tools. Regular expressions can be used to identify, search, edit, or replace text based on specific patterns.