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.
Concept
Regular language
Summary
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages).
Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars.
The collection of regular languages over an alphabet Σ is defined recursively as follows:
The empty language Ø is a regular language.
For each a ∈ Σ (a belongs to Σ), the singleton language {a } is a regular language.
If A is a regular language, A* (Kleene star) is a regular language. Due to this, the empty string language {ε} is also regular.
If A and B are regular languages, then A ∪ B (union) and A • B (concatenation) are regular languages.
No other languages over Σ are regular.
See regular expression for syntax and semantics of regular expressions.
All finite languages are regular; in particular the empty string language {ε} = Ø* is regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a's, or the language consisting of all strings of the form: several a's followed by several b's.
A simple example of a language that is not regular is the set of strings {anbn | n ≥ 0}. Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below.
Official source
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 publications (1)
Related concepts (48)
Automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM).
Regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton.
Regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory. The concept of regular expressions began in the 1950s, when the American mathematician Stephen Cole Kleene formalized the concept of a regular language.
Related courses (14)
MATH-305: Introduction to partial differential equations
This is an introductory course on Elliptic Partial Differential Equations. The course will cover the theory of both classical and generalized (weak) solutions of elliptic PDEs.
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
MATH-213: Differential geometry
Ce cours est une introduction à la géométrie différentielle classique des courbes et des surfaces, principalement dans le plan et l'espace euclidien.
Related lectures (116)
Construction of Solutions by Dirichlet-Laplace
Explores the construction of solutions by Dirichlet-Laplace in general domains.
Continuous Derivatives
Covers the concept of continuous derivatives and their application in analyzing functions and determining critical points.
Regularity of Weak Solutions
Explores elliptic PDEs, weak solutions, regularity, and strong solutions, with a focus on classical solutions and proof techniques.