nfadfa

Documentation

Index

• Variables
• type DFA
  • func (d *DFA) Print(out io.Writer)
• type DFAState
• type NFA
  • func NewNFA() *NFA
  • func (n *NFA) AddTransition(from, to *NFAState, input any) *NFAState
  • func (n *NFA) DFA() *DFA
  • func (n *NFA) NewState() *NFAState
  • func (n *NFA) Print(out io.Writer)
• type NFAState

Variables

var Epsilon = epsilon{}

Epsilon is the ε (empty string) input.

Types

type DFA

type DFA struct {
	Start  *DFAState
	States []*DFAState
}

func (*DFA) Print

func (d *DFA) Print(out io.Writer)

type DFAState

type DFAState struct {
	ID          uint32
	Transitions map[any]*DFAState
	Accept      bool
	NFAStates   []*NFAState
	Data        any
}

type NFA

type NFA struct {
	Start  *NFAState
	States []*NFAState
}

NFA represents a Nondeterministic Finite Automaton. https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton The NFA is state machine where: - A state is allowed to have multiple transitions for the same input. - The input ε (empty string) is allowed.

func NewNFA

func NewNFA() *NFA

NewNFA creates a new NFA.

func (*NFA) AddTransition

func (n *NFA) AddTransition(from, to *NFAState, input any) *NFAState

AddTransition adds a transition between two states on a given input. The input can be any comparable data, including Epsilon.

func (*NFA) DFA

func (n *NFA) DFA() *DFA

DFA converts the NFA into a DFA.

func (*NFA) NewState

func (n *NFA) NewState() *NFAState

NewState creates a new state in the NFA.

func (*NFA) Print

func (n *NFA) Print(out io.Writer)

type NFAState

type NFAState struct {
	// ID of the state.
	// It is assigned by the NFA and should be read-only.
	ID uint32

	// Transitions of the state.
	// Transitions should only be added using NFA.AddTransitions.
	Transitions map[any][]*NFAState

	// Accept indicates that the state machine should accept/recognize the input.
	// You set this yourself.
	Accept bool

	// Data is some user-data associated with this state.
	// Your set this yourself (or don't, I don't care).
	Data any
}

NFAState is a state in a NFA. NFAStates should only created using NFA.NewState().