watermill

README

watermill

Golang Implementation of Various Automata

Documentation

Index

• type Alphabet
  • func (ab Alphabet) Has(c rune) bool
  • func (ab Alphabet) HasAll(s string) bool
  • func (ab Alphabet) String() string
• type Automata
• type AutomataType
• type DeterministicFiniteAutomata
  • func NewDFA(name string, states []State, transDesc []TransitionDescription, start int64) (*DeterministicFiniteAutomata, error)
  • func (dfa *DeterministicFiniteAutomata) AcceptStates() []State
  • func (dfa *DeterministicFiniteAutomata) AcceptString(str string) (bool, error)
  • func (dfa *DeterministicFiniteAutomata) Alphabet() Alphabet
  • func (dfa *DeterministicFiniteAutomata) Name() string
  • func (dfa *DeterministicFiniteAutomata) StartState() State
  • func (dfa *DeterministicFiniteAutomata) TransitionGraph() *TransitionGraph
  • func (dfa *DeterministicFiniteAutomata) Type() AutomataType
  • func (dfa *DeterministicFiniteAutomata) Validate() error
• type FiniteAutomata
• type State
  • func (s State) ID() int64
  • func (s State) IsAccept() bool
  • func (s State) String() string
• type Transition
  • func (t *Transition) AllLabel() string
  • func (t Transition) From() graph.Node
  • func (t *Transition) HasLabel(l rune) bool
  • func (t Transition) ReversedEdge() graph.Edge
  • func (t Transition) To() graph.Node
• type TransitionDescription
• type TransitionGraph
  • func NewTransitionGraph(states []State, transDesc []TransitionDescription) (*TransitionGraph, error)
  • func (g *TransitionGraph) Edge(uid, vid int64) graph.Edge
  • func (g *TransitionGraph) From(id int64) graph.Nodes
  • func (g *TransitionGraph) GetTransitions(s State, l rune) ([]*Transition, error)
  • func (g *TransitionGraph) HasEdgeBetween(xid, yid int64) bool
  • func (g *TransitionGraph) HasEdgeFromTo(uid, vid int64) bool
  • func (g *TransitionGraph) HasState(s State) bool
  • func (g *TransitionGraph) Node(id int64) graph.Node
  • func (g *TransitionGraph) Nodes() graph.Nodes
  • func (g *TransitionGraph) States() []State
  • func (g *TransitionGraph) To(id int64) graph.Nodes

Types

type Alphabet

type Alphabet map[rune]bool

func (Alphabet) Has

func (ab Alphabet) Has(c rune) bool

func (Alphabet) HasAll

func (ab Alphabet) HasAll(s string) bool

func (Alphabet) String

func (ab Alphabet) String() string

type Automata

type Automata interface {
	Name() string
	Type() AutomataType
	TransitionGraph() TransitionGraph
	Alphabet() Alphabet
}

type AutomataType

type AutomataType uint

const (
	DFA AutomataType = iota
	NFA
	EpsilonNFA
)

type DeterministicFiniteAutomata

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

func NewDFA

func NewDFA(name string, states []State, transDesc []TransitionDescription, start int64) (*DeterministicFiniteAutomata, error)

func (*DeterministicFiniteAutomata) AcceptStates

func (dfa *DeterministicFiniteAutomata) AcceptStates() []State

func (*DeterministicFiniteAutomata) AcceptString

func (dfa *DeterministicFiniteAutomata) AcceptString(str string) (bool, error)

func (*DeterministicFiniteAutomata) Alphabet

func (dfa *DeterministicFiniteAutomata) Alphabet() Alphabet

func (*DeterministicFiniteAutomata) Name

func (dfa *DeterministicFiniteAutomata) Name() string

func (*DeterministicFiniteAutomata) StartState

func (dfa *DeterministicFiniteAutomata) StartState() State

func (*DeterministicFiniteAutomata) TransitionGraph

func (dfa *DeterministicFiniteAutomata) TransitionGraph() *TransitionGraph

func (*DeterministicFiniteAutomata) Type

func (dfa *DeterministicFiniteAutomata) Type() AutomataType

func (*DeterministicFiniteAutomata) Validate

func (dfa *DeterministicFiniteAutomata) Validate() error

type FiniteAutomata

type FiniteAutomata interface {
	Automata
	StartState() State
	AcceptStates() []State

	AcceptString(str string) (bool, error)
}

type State

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

func (State) ID

func (s State) ID() int64

func (State) IsAccept

func (s State) IsAccept() bool

func (State) String

func (s State) String() string

type Transition

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

func (*Transition) AllLabel

func (t *Transition) AllLabel() string

func (Transition) From

func (t Transition) From() graph.Node

func (*Transition) HasLabel

func (t *Transition) HasLabel(l rune) bool

func (Transition) ReversedEdge

func (t Transition) ReversedEdge() graph.Edge

func (Transition) To

func (t Transition) To() graph.Node

type TransitionDescription

type TransitionDescription struct {
	From  int64
	To    int64
	Label string
}

type TransitionGraph

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

func NewTransitionGraph

func NewTransitionGraph(states []State, transDesc []TransitionDescription) (*TransitionGraph, error)

func (*TransitionGraph) Edge

func (g *TransitionGraph) Edge(uid, vid int64) graph.Edge

func (*TransitionGraph) From

func (g *TransitionGraph) From(id int64) graph.Nodes

func (*TransitionGraph) GetTransitions

func (g *TransitionGraph) GetTransitions(s State, l rune) ([]*Transition, error)

func (*TransitionGraph) HasEdgeBetween

func (g *TransitionGraph) HasEdgeBetween(xid, yid int64) bool

func (*TransitionGraph) HasEdgeFromTo

func (g *TransitionGraph) HasEdgeFromTo(uid, vid int64) bool

func (*TransitionGraph) HasState

func (g *TransitionGraph) HasState(s State) bool

func (*TransitionGraph) Node

func (g *TransitionGraph) Node(id int64) graph.Node

func (*TransitionGraph) Nodes

func (g *TransitionGraph) Nodes() graph.Nodes

func (*TransitionGraph) States

func (g *TransitionGraph) States() []State

func (*TransitionGraph) To

func (g *TransitionGraph) To(id int64) graph.Nodes