Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Problems and Languages: Regular Languages

Description

This lecture covers regular languages, examples of problems related to regular languages, encoding, alphabets, words, languages, concatenation, exponentiation, and iterative closure. It also discusses the countability of effective procedures.

Official source

Ontological neighbourhood

Theoretical computer science

Programming language theory: Formal languages

Related concepts (32)

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.

Induction of regular languages

In computational learning theory, induction of regular languages refers to the task of learning a formal description (e.g. grammar) of a regular language from a given set of example strings. Although E. Mark Gold has shown that not every regular language can be learned this way (see language identification in the limit), approaches have been investigated for a variety of subclasses. They are sketched in this article. For learning of more general grammars, see Grammar induction.

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 grammar

In theoretical computer science and formal language theory, a regular grammar is a grammar that is right-regular or left-regular. While their exact definition varies from textbook to textbook, they all require that all production rules have at most one non-terminal symbol; that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a regular language.

Formal language

In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language. Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called well-formed words or well-formed formulas.

Related lectures (29)

Regular Expressions (Recap)

Covers the fundamentals of regular expressions and includes exercises on defining languages.

Operations on Formal Languages

Explores formal language operations, including concatenation, union, intersection, and Kleene star for language repetition.

Operations on Formal Languages

Covers formal languages, operations like union and concatenation, and the Kleene star operation.

Finite Automata: Basics

Introduces the basics of finite automata, including deterministic and non-deterministic types, regular expressions, and acceptance criteria.

Finite Automata: Recap