finite_automata

package
v0.0.0-...-e19c9e5 Latest Latest
Warning

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

Go to latest
Published: Oct 31, 2021 License: Apache-2.0 Imports: 3 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ConstructGraph

func ConstructGraph(inputArr []input_struct.EdgeInput) *ds.AdjGraph

func GenerateSubSets

func GenerateSubSets(faGraph *ds.AdjGraph, nodes []interface{}) *ds.MySet

GenerateSubSets C is union of all subsets 求子集依赖于底层的GraphAPI提供支持

func MinDFA

func MinDFA(nfa *ds.AdjGraph, startNodes []interface{}) *ds.AdjGraph

func NFAGenerateSubsetsAndConstructDFA

func NFAGenerateSubsetsAndConstructDFA(nfaGraph *ds.AdjGraph, startNodes []interface{}) (*ds.MySet, *ds.AdjGraph)

NFAGenerateSubsetsAndConstructDFA 为了消除 epsilonEdge

func NFAToDFA

func NFAToDFA(nfa *ds.AdjGraph, startNodes []interface{}) *ds.AdjGraph

func NFAToRegex

func NFAToRegex(faGraph *ds.AdjGraph) string

func NodeSetToIntValueSet

func NodeSetToIntValueSet(I *ISet) *ds.MySet

func RegexToNFA

func RegexToNFA(regex string) *ds.AdjGraph

func SubSetByOrder

func SubSetByOrder(C *ds.MySet) *ds.MySet

Types

type DFA

type DFA struct {
	S            *ISet // 有穷状态集合
	Sigma        *ISet // 输入符号表
	InitialState *ISet // 初始状态
	FinalState   *ISet // 终结状态
}

DFA Deterministic finite automata

func (*DFA) Delta

func (dfa *DFA) Delta(startState *ISet, edgeA *ISet) *ISet

Delta function f if Delta unction

type DFATable

type DFATable struct {
	State       *ISet
	Input       *ISet
	ChangeTable [][]interface{}
}

type IFA

type IFA interface {
	Delta(startState *ISet, edgeA *ISet) *ISet
}

type ISet

type ISet struct {
	CharSet *complicated.MySet
}

func EpsilonClosure

func EpsilonClosure(faGraph *ds.AdjGraph, I *ISet) *ISet

EpsilonClosure 集合I的所有状态经若干次空边到达的状态 并上 集合I

func Move

func Move(faGraph *ds.AdjGraph, I *ISet, a interface{}) *ISet

Move 集合I的所有状态经过一次a边到达的状态

func SeparateOnlySetValue

func SeparateOnlySetValue(I *ISet) *ISet

func (*ISet) CheckSelf

func (iset *ISet) CheckSelf() bool

func (*ISet) Construct

func (iset *ISet) Construct()

func (*ISet) String

func (iset *ISet) String() string

type NFA

type NFA struct {
	S            *ISet
	Sigma        *ISet
	InitialState *ISet
	FinalState   *ISet
	// contains filtered or unexported fields
}

NFA NonDeterministic finite automata

func (*NFA) Delta

func (nfa *NFA) Delta(startState *ISet, edgeA *ISet) *ISet

Delta is Edge Description

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL