automata

package
v0.11.0 Latest Latest
Warning

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

 Go to latest Published: Feb 22, 2025 License: ISC Imports: 11 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)
)

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 {
	Start State
	Final States
	// contains filtered or unexported fields
}

DFA implements a deterministic finite automaton.

func CombineDFA added in v0.11.0 

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

CombineDFA merges multiple deterministic finite automata (DFAs) into a single DFA that recognizes the union of the languages accepted by each individual DFA.

The process follows these steps:

  1. Convert each DFA into a nondeterministic finite automaton (NFA).
  2. Construct a single NFA that accepts the union of all individual NFAs.
  3. Convert the unified NFA into a DFA.
  4. Remove dead states and eliminate transitions leading to them.
  5. Reassign state indices to maintain a compact representation.

Throughout this process, the method tracks the final states of each original DFA, returning a slice where each index maps to the final states of the corresponding DFA.

Note: This method does not minimize the resulting DFA, as minimization would merge final states, making it impossible to distinguish between the final states of the individual DFAs.

This function is commonly used when constructing a DFA for lexical analysis.

func NewDFA 

func NewDFA(start State, final []State) *DFA

NewDFA creates a new deterministic finite automaton. Finite automata are recognizers; they simply say yes or no for each possible input string.

func (*DFA) Accept 

func (d *DFA) Accept(s String) bool

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

func (*DFA) Add added in v0.3.5 

func (d *DFA) Add(s State, a Symbol, next State)

Add inserts a new transition into the DFA.

func (*DFA) Clone added in v0.11.0 

func (d *DFA) Clone() *DFA

Clone returns a deep copy of the DFA, ensuring the clone is independent of the original.

func (*DFA) DOT added in v0.10.0 

func (d *DFA) DOT() string

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

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 determines whether or not two DFAs are identical in structure and labeling. Two DFAs are considered equal if they have the same start state, final states, and transitions.

For isomorphic equality, structural equivalence with potentially different state names, use the Isomorphic method.

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.

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) Next added in v0.3.5 

func (d *DFA) Next(s State, a Symbol) State

Next returns the next state based on the current state s and the input symbol a. If no valid transition exists, it returns an invalid state (-1).

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) States added in v0.3.5 

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

States returns the set of all states of the DFA.

func (*DFA) String added in v0.11.0 

func (d *DFA) String() string

String returns a string representation of the DFA.

func (*DFA) Symbols added in v0.3.5 

func (d *DFA) Symbols() []Symbol

Symbols returns the set of all input symbols of 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.Seq[*Transition[State]]

Transitions returns an iterator sequence containing all transitions in the DFA.

type NFA 

type NFA struct {
	Start State
	Final States
	// contains filtered or unexported fields
}

NFA implements a non-deterministic finite automaton.

func NewNFA 

func NewNFA(start State, final []State) *NFA

NewNFA creates a new non-deterministic finite automaton. Finite automata are recognizers; they simply say yes or no for each possible input string.

func (*NFA) Accept 

func (n *NFA) Accept(s String) bool

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

func (*NFA) Add added in v0.3.5 

func (n *NFA) Add(s State, a Symbol, next []State)

Add inserts a new transition into the NFA.

func (*NFA) Clone added in v0.11.0 

func (n *NFA) Clone() *NFA

Clone returns a deep copy of the NFA, ensuring the clone is independent of the original.

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 transition graph of the NFA.

func (*NFA) Equal added in v0.10.3 

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

Equal determines whether or not two NFAs are identical in structure and labeling. Two NFAs are considered equal if they have the same start state, final states, and transitions.

For isomorphic equality, structural equivalence with potentially different state names, use the Isomorphic method.

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.

func (*NFA) Next added in v0.3.5 

func (n *NFA) Next(s State, a Symbol) []State

Next returns the set of next states based on the current state s and the input symbol a. If no valid transition exists, it returns nil

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) States added in v0.3.5 

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

States returns the set of all states of the NFA.

func (*NFA) String added in v0.11.0 

func (n *NFA) String() string

String returns a string representation of the NFA.

func (*NFA) Symbols added in v0.3.5 

func (n *NFA) Symbols() []Symbol

Symbols returns the set of all input symbols of 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.

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

func (*NFA) Transitions added in v0.11.0 

func (n *NFA) Transitions() iter.Seq[*Transition[[]State]]

Transitions returns an iterator sequence containing all transitions 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 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 = 0

E is the empty string ε and is never a member of an input alphabet Σ.

type Symbols 

type Symbols set.Set[Symbol]

Symbols represents a set of symbols in an automaton.

type Transition added in v0.11.0 

type Transition[T State | []State] struct {
	State
	Symbol
	Next T
}

Transition represents a transition in a finite automaton. It can be either a DFA transition with a single next state or an NFA transition with multiple next states.

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.