Regular language | 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 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.

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)

Related courses (14)

Related lectures (116)

An Algorithm Architecture Co-Design for CMOS Compressive High Dynamic Range Imaging

Pierre Vandergheynst, William Guicquéro, Antoine Dupret

Standard image sensors feature dynamic range about 60 to 70 dB while the light flux of natural scenes may be over 120 dB. Most imagers dedicated to address such dynamic ranges, need specific, and larg

Ieee-Inst Electrical Electronics Engineers Inc2016

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.

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

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.

Construction of Solutions by Dirichlet-Laplace MATH-305: Introduction to partial differential equations

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 MATH-305: Introduction to partial differential equations

Explores elliptic PDEs, weak solutions, regularity, and strong solutions, with a focus on classical solutions and proof techniques.