automata

package
v0.12.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 6, 2025 License: ISC Imports: 13 Imported by: 0

README

Automata

Finite automata are recognizers; they simply say yes or no for each possible input string. They come in two flavors:

  • Deterministic finite automata (DFA)
  • Non-deterministic finite automata (NFA)

Documentation

Overview

Package automata provides data structures and algorithms for working with automata.

In language theory, automata refer to abstract computational models used to define and study formal languages. Automata are mathematical structures that process input strings and determine whether they belong to a specific language.

Index

Constants

This section is empty.

Variables

View Source 
var (
	EqState   = generic.NewEqualFunc[State]()
	CmpState  = generic.NewCompareFunc[State]()
	HashState = hash.HashFuncForInt[State](nil)

	EqSymbol   = generic.NewEqualFunc[Symbol]()
	CmpSymbol  = generic.NewCompareFunc[Symbol]()
	HashSymbol = hash.HashFuncForInt32[Symbol](nil)

	EqStates = func(a, b States) bool {
		if a == nil && b == nil {
			return true
		}

		if a == nil || b == nil {
			return false
		}

		return a.Equal(b)
	}

	CmpStates = func(a, b States) int {
		if a == nil && b == nil {
			return 0
		} else if a == nil {
			return -1
		} else if b == nil {
			return 1
		}

		lhs := generic.Collect1(a.All())
		rhs := generic.Collect1(b.All())

		for i := 0; i < len(lhs) && i < len(rhs); i++ {
			if c := CmpState(lhs[i], rhs[i]); c != 0 {
				return c
			}
		}

		return len(lhs) - len(rhs)
	}

	EqSymbols = func(a, b Symbols) bool {
		if a == nil && b == nil {
			return true
		}

		if a == nil || b == nil {
			return false
		}

		return a.Equal(b)
	}
)

Functions

func NewSymbols added in v0.11.0 

func NewSymbols(a ...Symbol) set.Set[Symbol]

NewSymbols creates a new set of symbols, initialized with the given symbols.

Types

type DFA 

type DFA struct {
	// contains filtered or unexported fields
}

DFA represents a deterministic finite automaton.

A DFA is defined by a 5-tuple (Q, Σ, δ, q₀, F) where:

  • Q is a finite set of states.
  • Σ is a finite set of input symbols (alphabet).
  • δ: Q × Σ → Q is the transition function.
  • q₀ ∈ Q is the initial (start) state.
  • F ⊆ Q is the set of accepting (final) states.

This model is meant to be an immutable representation of deterministic finite automata. Algorithms that transform or optimize a DFA must construct and return a new DFA.

func UnionDFA added in v0.12.1 

func UnionDFA(ds ...*DFA) (*DFA, [][]State)

UnionDFA constructs a DFA that recognizes the union of the languages accepted by the provided DFAs.

The process involves:

  1. Converting each DFA to an NFA.
  2. Building a single NFA that accepts the union of all input NFAs.
  3. Converting the unified NFA to a DFA.
  4. Removing dead states and transitions to them.
  5. Reindexing states to maintain a compact representation.

The returned DFA accepts any string accepted by at least one input DFA. The second return value maps each input DFA to its corresponding final states in the resulting DFA.

Note: The resulting DFA is not minimized, so final states remain distinguishable for each input DFA. This is useful for applications like lexical analysis, where tracking the origin of acceptance matters.

func (*DFA) Clone added in v0.11.0 

func (d *DFA) Clone() *DFA

Clone implements the generic.Cloner interface.

func (*DFA) DOT added in v0.10.0 

func (d *DFA) DOT() string

DOT generates a DOT representation of the DFA transition graph for visualization.

func (*DFA) EliminateDeadStates added in v0.11.0 

func (d *DFA) EliminateDeadStates() *DFA

EliminateDeadStates eliminates the dead states and all transitions to them. The subset construction and minimization algorithms sometimes produce a DFA with a single dead state.

Strictly speaking, a DFA must have a transition from every state on every input symbol in its input alphabet. When we construct a DFA to be used in a lexical analyzer, we need to treat the dead state differently. We must know when there is no longer any possibility of recognizing a longer lexeme. Thus, we should always omit transitions to the dead state and eliminate the dead state itself.

func (*DFA) Equal added in v0.10.3 

func (d *DFA) Equal(rhs *DFA) bool

Equal implements the generic.Equaler interface.

func (*DFA) Final added in v0.3.5 

func (d *DFA) Final() []State

Final returns the final (accepting) states of the DFA.

func (*DFA) Isomorphic added in v0.8.1 

func (d *DFA) Isomorphic(rhs *DFA) bool

Isomorphic determines whether or not two DFAs are isomorphically the same.

Two DFAs D₁ and D₂ are said to be isomorphic if there exists a bijection f: S(D₁) → S(D₂) between their state sets such that, for every input symbol a, there is a transition from state s to state t on input a in D₁ if and only if there is a transition from state f(s) to state f(t) on input a in D₂.

In simpler terms, the two DFAs have the same structure: one can be transformed into the other by renaming its states and preserving the transitions.

This is a very expensive operation as graph isomorphism problem is an NP (non-deterministic polynomial time) problem.

func (*DFA) Minimize added in v0.4.2 

func (d *DFA) Minimize() *DFA

Minimize creates a unique DFA with the minimum number of states.

The minimization algorithm sometimes produces a DFA with one dead state. This state is not accepting and transfers to itself on each input symbol.

We often want to know when there is no longer any possibility of acceptance. If so, we may want to eliminate the dead state and use an automaton that is missing some transitions. This automaton has one fewer state than the minimum-state DFA. Strictly speaking, such an automaton is not a DFA, because of the missing transitions to the dead state.

For more information and details, see "Compilers: Principles, Techniques, and Tools (2nd Edition)".

func (*DFA) ReindexStates added in v0.11.0 

func (d *DFA) ReindexStates() *DFA

ReindexStates reassigns indices to states based on a breadth-first traversal of the DFA, starting from the initial state. This method is typically called after removing unreachable or dead states from the DFA.

func (*DFA) Runner added in v0.12.0 

func (d *DFA) Runner() *DFARunner

Runner constructs a new DFARunner for simulating (running) the DFA on input symbols.

func (*DFA) Start added in v0.3.5 

func (d *DFA) Start() State

Start returns the start state of the DFA.

func (*DFA) States added in v0.3.5 

func (d *DFA) States() []State

States returns all states in the DFA.

func (*DFA) String added in v0.11.0 

func (d *DFA) String() string

String implements the fmt.Stringer interface.

func (*DFA) Symbols added in v0.3.5 

func (d *DFA) Symbols() []disc.Range[Symbol]

Symbols returns all symbol ranges in the DFA.

func (*DFA) ToNFA added in v0.4.2 

func (d *DFA) ToNFA() *NFA

ToNFA constructs a new NFA accepting the same language as the DFA (every DFA is an NFA).

func (*DFA) Transitions added in v0.11.0 

func (d *DFA) Transitions() iter.Seq2[State, iter.Seq2[[]disc.Range[Symbol], State]]

Transitions returns all transitions in the DFA.

func (*DFA) TransitionsFrom added in v0.12.0 

func (d *DFA) TransitionsFrom(s State) iter.Seq2[[]disc.Range[Symbol], State]

TransitionsFrom returns all transitions from the given state in the DFA.

func (*DFA) Union added in v0.12.0 

func (d *DFA) Union(ds ...*DFA) (*DFA, [][]State)

Union constructs a DFA that recognizes the union of the languages accepted by the provided DFAs.

The process involves:

  1. Converting each DFA to an NFA.
  2. Building a single NFA that accepts the union of all input NFAs.
  3. Converting the unified NFA to a DFA.
  4. Removing dead states and transitions to them.
  5. Reindexing states to maintain a compact representation.

The returned DFA accepts any string accepted by at least one input DFA. The second return value maps each input DFA to its corresponding final states in the resulting DFA.

Note: The resulting DFA is not minimized, so final states remain distinguishable for each input DFA. This is useful for applications like lexical analysis, where tracking the origin of acceptance matters.

type DFABuilder added in v0.12.0 

type DFABuilder struct {
	// contains filtered or unexported fields
}

DFABuilder implements the Builder design pattern for constructing DFA instances.

The Builder pattern separates the construction of a DFA from its representation. This approach ensures the resulting DFA is immutable and optimized for simulation (running).

func NewDFABuilder added in v0.12.0 

func NewDFABuilder() *DFABuilder

NewDFABuilder creates a new DFA builder instance.

func (*DFABuilder) AddTransition added in v0.12.0 

func (b *DFABuilder) AddTransition(s State, start, end Symbol, next State) *DFABuilder

AddTransition adds transitions from state s to state next on all input symbols in the range [start, end].

func (*DFABuilder) Build added in v0.12.0 

func (b *DFABuilder) Build() *DFA

Build constructs the DFA based on the configurations provided to the builder.

This method reduces the size of the alphabet by computing the equivalence classes of input symbols based on the transition function. The resulting DFA will recognize the same language, but with a minimized alphabet optimized for faster simulation and smaller memory footprint.

Formally, given a DFA = (Q, Σ, δ, q₀, F), we want compute a partition of Σ into k equivalence classes such that 

P = {C₁, C₂, ..., Cₖ} where each Cᵢ ⊆ Σ and ∪ Cᵢ = Σ
∀ a, b ∈ Cᵢ, ∀ q ∈ Q: δ(q, a) = δ(q, b)

Informally, two symbols are equivalent if they lead to the same next state from any given state (every state treats them the same).

func (*DFABuilder) SetFinal added in v0.12.0 

func (b *DFABuilder) SetFinal(f []State) *DFABuilder

SetFinal sets the final (accepting) states of the DFA.

func (*DFABuilder) SetStart added in v0.12.0 

func (b *DFABuilder) SetStart(s State) *DFABuilder

SetStart sets the start state of the DFA.

type DFARunner added in v0.12.0 

type DFARunner struct {
	// contains filtered or unexported fields
}

DFARunner is used for simulating (running) a DFA on input symbols. It is immutable and optimized for fast execution.

func (*DFARunner) Accept added in v0.12.0 

func (r *DFARunner) Accept(s String) bool

Accept determines whether an input string is recognized (accepted) by the DFA.

func (*DFARunner) Next added in v0.12.0 

func (r *DFARunner) Next(s State, a Symbol) State

Next returns the next state from state s on input symbol a.

type NFA 

type NFA struct {
	// contains filtered or unexported fields
}

NFA represents a non-deterministic finite automaton.

A NFA is defined by a 5-tuple (Q, Σ, δ, q₀, F) where:

  • Q is a finite set of states.
  • Σ is a finite set of input symbols (alphabet).
  • δ: Q × Σ → P(Q) is the transition function.
  • q₀ ∈ Q is the initial (start) state.
  • F ⊆ Q is the set of accepting (final) states.

This model is meant to be an immutable representation of non-deterministic finite automata. Algorithms that transform or optimize a NFA must construct and return a new NFA.

func ConcatNFA added in v0.12.1 

func ConcatNFA(ns ...*NFA) *NFA

ConcatNFA constructs a new NFA that accepts the concatenation of languages accepted by each individual NFA.

func UnionNFA added in v0.12.1 

func UnionNFA(ns ...*NFA) *NFA

UnionNFA constructs a new NFA that accepts the union of languages accepted by each individual NFA.

func (*NFA) Clone added in v0.11.0 

func (n *NFA) Clone() *NFA

Clone implements the generic.Cloner interface.

func (*NFA) Concat added in v0.4.3 

func (n *NFA) Concat(ns ...*NFA) *NFA

Concat constructs a new NFA that accepts the concatenation of languages accepted by each individual NFA.

func (*NFA) DOT added in v0.10.0 

func (n *NFA) DOT() string

DOT generates a DOT representation of the NFA transition graph for visualization.

func (*NFA) Equal added in v0.10.3 

func (n *NFA) Equal(rhs *NFA) bool

Equal implements the generic.Equaler interface.

func (*NFA) Final added in v0.3.5 

func (n *NFA) Final() []State

Final returns the final (accepting) states of the NFA.

func (*NFA) Isomorphic added in v0.8.1 

func (n *NFA) Isomorphic(rhs *NFA) bool

Isomorphic determines whether or not two NFAs are isomorphically the same.

Two NFAs N₁ and N₂ are said to be isomorphic if there exists a bijection f: S(N₁) → S(N₂) between their state sets such that, for every input symbol a, there is a transition from state s to state t on input a in N₁ if and only if there is a transition from state f(s) to state f(t) on input a in N₂.

In simpler terms, the two NFAs have the same structure: one can be transformed into the other by renaming its states and preserving the transitions.

This is a very expensive operation as graph isomorphism problem is an NP (non-deterministic polynomial time) problem.

func (*NFA) Runner added in v0.12.0 

func (n *NFA) Runner() *NFARunner

Runner constructs a new NFARunner for simulating (running) the NFA on input symbols.

func (*NFA) Star added in v0.4.4 

func (n *NFA) Star() *NFA

Star constructs a new NFA that accepts the Kleene star closure of the language accepted by the NFA.

func (*NFA) Start added in v0.3.5 

func (n *NFA) Start() State

Start returns the start state of the NFA.

func (*NFA) States added in v0.3.5 

func (n *NFA) States() []State

States returns all states in the NFA.

func (*NFA) String added in v0.11.0 

func (n *NFA) String() string

String implements the fmt.Stringer interface.

func (*NFA) Symbols added in v0.3.5 

func (n *NFA) Symbols() []disc.Range[Symbol]

Symbols returns all symbol ranges in the NFA.

func (*NFA) ToDFA 

func (n *NFA) ToDFA() *DFA

ToDFA constructs a new DFA accepting the same language as the NFA. It implements the subset construction algorithm.

func (*NFA) Transitions added in v0.11.0 

func (n *NFA) Transitions() iter.Seq2[State, iter.Seq2[[]disc.Range[Symbol], []State]]

Transitions returns all transitions in the NFA.

func (*NFA) TransitionsFrom added in v0.12.0 

func (n *NFA) TransitionsFrom(s State) iter.Seq2[[]disc.Range[Symbol], []State]

TransitionsFrom returns all transitions from the given state in the NFA.

func (*NFA) Union added in v0.4.3 

func (n *NFA) Union(ns ...*NFA) *NFA

Union constructs a new NFA that accepts the union of languages accepted by each individual NFA.

type NFABuilder added in v0.12.0 

type NFABuilder struct {
	// contains filtered or unexported fields
}

NFABuilder implements the Builder design pattern for constructing NFA instances.

The Builder pattern separates the construction of an NFA from its representation, This approach ensures the resulting NFA is immutable and optimized for simulation (running).

func NewNFABuilder added in v0.12.0 

func NewNFABuilder() *NFABuilder

NewNFABuilder creates a new NFA builder instance.

func (*NFABuilder) AddTransition added in v0.12.0 

func (b *NFABuilder) AddTransition(s State, start, end Symbol, next []State) *NFABuilder

AddTransition adds transitions from state s to states next on all input symbols in the range [start, end].

func (*NFABuilder) Build added in v0.12.0 

func (b *NFABuilder) Build() *NFA

Build constructs the NFA based on the configurations provided to the builder.

This method reduces the size of the alphabet by computing the equivalence classes of input symbols based on the transition function. The resulting NFA will recognize the same language, but with a minimized alphabet optimized for faster simulation and smaller memory footprint.

Formally, given a NFA = (Q, Σ, δ, q₀, F), we want compute a partition of Σ into k equivalence classes such that 

P = {C₁, C₂, ..., Cₖ} where each Cᵢ ⊆ Σ and ∪ Cᵢ = Σ
∀ a, b ∈ Cᵢ, ∀ q ∈ Q: δ(q, a) = δ(q, b)

Informally, two symbols are equivalent if they lead to the same next state from any given state (every state treats them the same).

func (*NFABuilder) SetFinal added in v0.12.0 

func (b *NFABuilder) SetFinal(f []State) *NFABuilder

SetFinal sets the final (accepting) states of the NFA.

func (*NFABuilder) SetStart added in v0.12.0 

func (b *NFABuilder) SetStart(s State) *NFABuilder

SetStart sets the start state of the NFA.

type NFARunner added in v0.12.0 

type NFARunner struct {
	// contains filtered or unexported fields
}

NFARunner is used for simulating (running) a NFA on input symbols. It is immutable and optimized for fast execution.

func (*NFARunner) Accept added in v0.12.0 

func (r *NFARunner) Accept(s String) bool

Accept determines whether an input string is recognized (accepted) by the NFA.

func (*NFARunner) Next added in v0.12.0 

func (r *NFARunner) Next(s State, a Symbol) []State

Next returns the next states from state s on input symbol a.

type State 

type State int

State represents a state in an automaton, identified by an integer.

type States 

type States set.Set[State]

States represents a set of states in an automaton.

func NewStates added in v0.11.0 

func NewStates(s ...State) States

NewStates creates a new set of states, initialized with the given states.

type String 

type String []Symbol

String represents a sequence of symbols in an automaton.

type Symbol 

type Symbol rune

Symbol represents an input symbol in an automaton, identified by a rune. 

const E Symbol = -1

E is the empty string ε and is never a member of an input alphabet Σ. It is intentionally chosen outside the Unicode range to avoid conflicts with valid symbols.

type Symbols 

type Symbols set.Set[Symbol]

Symbols represents a set of symbols in an automaton.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.