mathlib documentation

computability.DFA

Deterministic Finite Automata #

This file contains the definition of a Deterministic Finite Automaton (DFA), a state machine which determines whether a string (implemented as a list over an arbitrary alphabet) is in a regular set in linear time. Note that this definition allows for Automaton with infinite states, a fintype instance must be supplied for true DFA's.

source
structure DFA (α : Type u) (σ : Type v) :
Type (max u v)
  • step : σ → α → σ
  • start : σ
  • accept : set σ

A DFA is a set of states (σ), a transition function from state to state labelled by the alphabet (step), a starting state (start) and a set of acceptance states (accept).

source
@[instance]
def DFA.inhabited {α : Type u} {σ : Type v} [inhabited σ] :
inhabited (DFA α σ)
Equations
source
def DFA.eval_from {α : Type u} {σ : Type v} (M : DFA α σ) (start : σ) :
list α → σ

M.eval_from s x evaluates M with input x starting from the state s.

Equations
source
def DFA.eval {α : Type u} {σ : Type v} (M : DFA α σ) :
list α → σ

M.eval x evaluates M with input x starting from the state M.start.

Equations
source
def DFA.accepts {α : Type u} {σ : Type v} (M : DFA α σ) :
language α

M.accepts is the language of x such that M.eval x is an accept state.

Equations
source
theorem DFA.mem_accepts {α : Type u} {σ : Type v} (M : DFA α σ) (x : list α) :
x ∈ M.accepts ↔ M.eval_from M.start x ∈ M.accept
source
theorem DFA.eval_from_of_append {α : Type u} {σ : Type v} (M : DFA α σ) (start : σ) (x y : list α) :
M.eval_from start (x ++ y) = M.eval_from (M.eval_from start x) y
source
theorem DFA.eval_from_split {α : Type u} {σ : Type v} (M : DFA α σ) [fintype σ] {x : list α} {s t : σ} (hlen : fintype.card σ + 1 ≤ x.length) (hx : M.eval_from s x = t) :
∃ (q : σ) (a b c : list α), x = a ++ b ++ c ∧ a.length + b.length ≤ fintype.card σ + 1 ∧ b ≠ list.nil ∧ M.eval_from s a = q ∧ M.eval_from q b = q ∧ M.eval_from q c = t
source
theorem DFA.eval_from_of_pow {α : Type u} {σ : Type v} (M : DFA α σ) {x y : list α} {s : σ} (hx : M.eval_from s x = s) (hy : y ∈ {x}.star) :
M.eval_from s y = s
source
theorem DFA.pumping_lemma {α : Type u} {σ : Type v} (M : DFA α σ) [fintype σ] {x : list α} (hx : x ∈ M.accepts) (hlen : fintype.card σ + 1 ≤ x.length) :
∃ (a b c : list α), x = a ++ b ++ c ∧ a.length + b.length ≤ fintype.card σ + 1 ∧ b ≠ list.nil ∧ ({a} * {b}.star) * {c} ≤ M.accepts