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

Lecture

Regular Expressions (Recap)

Description

This lecture covers the fundamentals of regular expressions, including finite automata, the pumping lemma, and exercises on defining languages with regular expressions. It also delves into examples and proofs related to regular languages.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Automata theory

Related concepts (32)

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

Deterministic finite automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run.

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.

Alternating finite automaton

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton. For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton. For a universal transition , A moves to and , reading a, simulating the behavior of a parallel machine.

Related lectures (41)

Finite Automata: Basics

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

From Regular Expressions to Automata

Explores the transition from regular expressions to finite automata, covering lexer creation, different automata types, and conversion processes.

Finite Automata: Recap

Covers the fundamentals of finite automata and formal languages.

Context-Free Grammars

Covers context-free grammars, their equivalence to pushdown automata, and the hierarchy of grammar types.

Automata Theory: Basics and Theorems