nfa

Documentation

Overview

Package nfa implements Non-Deterministic Finite Automaton(NFA).

Index

• type DFAStatesMap
• type NFA
  • func NewNFA(init utils.State, accepts mapset.Set, rules nfarule.RuleMap) *NFA
  • func (nfa *NFA) AllSymbol() mapset.Set
  • func (nfa *NFA) CalcDst(q utils.State, c rune) (mapset.Set, bool)
  • func (nfa *NFA) SubsetConstruction() (dI utils.State, dF mapset.Set, dRules dfarule.RuleMap)
  • func (nfa *NFA) ToWithoutEpsilon()

Types

type DFAStatesMap

type DFAStatesMap map[mapset.Set]utils.State

DFAStatesMap associates subsets of the NFA state set with the states of the DFA.

type NFA

type NFA struct {
	I     utils.State     // initial state
	F     mapset.Set      // accept states
	Rules nfarule.RuleMap // transition function
}

NFA represents a Non-Deterministic Finite Automaton.

func NewNFA

func NewNFA(init utils.State, accepts mapset.Set, rules nfarule.RuleMap) *NFA

NewNFA returns a new NFA.

func (*NFA) AllSymbol

func (nfa *NFA) AllSymbol() mapset.Set

AllSymbol returns a set of the all "Symbol" in Rule.

func (*NFA) CalcDst

func (nfa *NFA) CalcDst(q utils.State, c rune) (mapset.Set, bool)

CalcDst returns, according to the transition function, a set of states to which transition is executed when c is received in the state of argument q.

func (*NFA) SubsetConstruction

func (nfa *NFA) SubsetConstruction() (dI utils.State, dF mapset.Set, dRules dfarule.RuleMap)

subsetConstruction implements Subset Construction. Returns the data for constructing the equivalent DFA from the NFA given in the argument. For details: https://en.wikipedia.org/wiki/Powerset_construction

func (*NFA) ToWithoutEpsilon

func (nfa *NFA) ToWithoutEpsilon()

ToWithoutEpsilon update ε-NFA to NFA whose no epsilon transitions.