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

Lecture

Finite Automata: Basics

Description

This lecture covers the basics of finite automata, including deterministic and non-deterministic finite automata, regular expressions, formal definitions, acceptance criteria, and derivability. The instructor explains the concepts step by step, providing examples and clarifications.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Automata theory

Related concepts (28)

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.

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.

Two-way finite automaton

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input. A two-way deterministic finite automaton (2DFA) is an abstract machine, a generalized version of the deterministic finite automaton (DFA) which can revisit characters already processed. As in a DFA, there are a finite number of states with transitions between them based on the current character, but each transition is also labelled with a value indicating whether the machine will move its position in the input to the left, right, or stay at the same position.

Quantum finite automaton

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

Related lectures (33)

Regular Expressions (Recap)

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

From Regular Expressions to Automata

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

Automata Theory: Basics and Theorems

Introduces the basics of automata theory and explores the theorems of regular languages.

Context-Free Grammars

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

Finite Automata: Recap