README
¶
fsm
Package fsm provides utilities for messing with finite state machines.
Installation
$ go get github.com/cznic/fsm
Documentation: godoc.org/github.com/cznic/fsm
Documentation
¶
Overview ¶
Package fsm provides some utilities for messing with finite state machines.
Dead DFA State ¶
"A state is a dead state if it is not an accepting state and has no out-going transitions except to itself."[7]
Passing withDeadState == true to some methods in this package makes the produced DFAs "complete". For many practical purposes the dead state is not needed and all the additional edges to it are only a waste of memory.
Note: Negative symbol values are reserved for internal purposes.
TODO ¶
Implement ε edges having other than the default priority (Epsilon == -1). This is needed for regexp based recognizers/tokenizers like golex[8].
Index ¶
- Constants
- type Closure
- type NFA
- func (n *NFA) Equals(m *NFA) bool
- func (n *NFA) Len() int
- func (n *NFA) List() (r []*State)
- func (n *NFA) MinimalDFA(withDeadState bool) *NFA
- func (n *NFA) NewState() *State
- func (n *NFA) Powerset(withDeadState bool) (out *NFA)
- func (n *NFA) Reverse() (out *NFA)
- func (n *NFA) SetStart(s *State)
- func (n *NFA) Start() *State
- func (n *NFA) State(id int) *State
- func (n *NFA) String() string
- type State
- type Transitions
Examples ¶
Constants ¶
const Epsilon = -1
Epsilon is a symbol value representing an ε edge (with no priority).
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Closure ¶
type Closure struct {
// contains filtered or unexported fields
}
Closure is a set of states.
func (Closure) Exclude ¶
func (c Closure) Exclude(s *State)
Exclude removes state s from the closure.
type NFA ¶
type NFA struct {
// contains filtered or unexported fields
}
NFA is a nondeterministic finite automaton [2].
func ParseRegex ¶
ParseRegex parses a regular expression and returns an NFA that accepts the same language. The actual parsing legwork is done by Go's regexp/syntax package; ParseRegex traverses the AST generated by regexp/syntax and compiles the AST into an NFA. An important precondition is that, since regexp/syntax was designed to work on printable strings, the transitions in the output NFA are "runes", which are equivalent to int32.
func (*NFA) Equals ¶
Equals returns wheter m accepts the same language as n.
Example ¶
// The two NFAs are shown here: http://cs.stackexchange.com/a/12694/989
//
// Instead of symbols {a,b,c} we will here use {0,1,2}, so the accepted
// language is {01,02,12,10,20,21}.
n := NewNFA()
n0, n1, n2, n3, n4 := n.NewState(), n.NewState(), n.NewState(), n.NewState(), n.NewState()
n0.NewEdge(0, n2)
n0.NewEdge(0, n3)
n0.NewEdge(1, n1)
n0.NewEdge(1, n3)
n0.NewEdge(2, n1)
n0.NewEdge(2, n2)
n1.NewEdge(0, n4)
n2.NewEdge(1, n4)
n3.NewEdge(2, n4)
n4.IsAccepting = true
m := NewNFA()
m0, m1, m2, m3, m4 := m.NewState(), m.NewState(), m.NewState(), m.NewState(), m.NewState()
m0.NewEdge(0, m1)
m0.NewEdge(1, m2)
m0.NewEdge(2, m3)
m1.NewEdge(1, m4)
m1.NewEdge(2, m4)
m2.NewEdge(0, m4)
m2.NewEdge(2, m4)
m3.NewEdge(0, m4)
m3.NewEdge(1, m4)
m4.IsAccepting = true
fmt.Printf("NFA1\n%v\nNFA2\n%v\nEquals: %t", n, m, n.Equals(m))
Output: NFA1 ->[0] 0 -> [2] [3] 1 -> [1] [3] 2 -> [1] [2] [1] 0 -> [4] [2] 1 -> [4] [3] 2 -> [4] [[4]] NFA2 ->[0] 0 -> [1] 1 -> [2] 2 -> [3] [1] 1 -> [4] 2 -> [4] [2] 0 -> [4] 2 -> [4] [3] 0 -> [4] 1 -> [4] [[4]] Equals: true
func (*NFA) MinimalDFA ¶
MinimalDFA returns the NFA converted to a minimal DFA[5]. Dead state is possibly constructed if withDeadState == true.
Note: Algorithm used is Brzozowski[6].
Example ¶
n := NewNFA() // NFA for regexp `012|12|02` s0, s1, s2, s3, s4, s5 := n.NewState(), n.NewState(), n.NewState(), n.NewState(), n.NewState(), n.NewState() s0.NewEdge(0, s1) s0.NewEdge(0, s5) s0.NewEdge(1, s4) s1.NewEdge(1, s2) s2.NewEdge(2, s3) s3.IsAccepting = true s4.NewEdge(2, s3) s5.NewEdge(2, s3) fmt.Printf( "NFA\n%v\nDFA\n%v\nMinimal DFA\n%v\nMinimal DFA with a dead state\n%v", n, n.Powerset(false), n.MinimalDFA(false), n.MinimalDFA(true), )
Output: NFA ->[0] 0 -> [1] [5] 1 -> [4] [1] 1 -> [2] [2] 2 -> [3] [[3]] [4] 2 -> [3] [5] 2 -> [3] DFA ->[0] 0 -> [1] 1 -> [4] [1] 1 -> [2] 2 -> [3] [2] 2 -> [3] [[3]] [4] 2 -> [3] Minimal DFA ->[0] 0 -> [3] 1 -> [1] [1] 2 -> [2] [[2]] [3] 1 -> [1] 2 -> [2] Minimal DFA with a dead state ->[0] 0 -> [3] 1 -> [1] 2 -> [4] [1] 0 -> [4] 1 -> [4] 2 -> [2] [[2]] 0 -> [4] 1 -> [4] 2 -> [4] [3] 0 -> [4] 1 -> [1] 2 -> [2] [4] 0 -> [4] 1 -> [4] 2 -> [4]
func (*NFA) NewState ¶
NewState returns a new state added to the NFA. If the NFA was empty, the new state becomes the start state.
func (*NFA) Powerset ¶
Powerset converts[3] the NFA into a NFA without ε edges, ie. into a DFA. Dead state is possibly constructed if withDeadState == true.
Example ¶
// See http://en.wikipedia.org/wiki/Powerset_construction#Example
n := NewNFA()
s1, s2, s3, s4 := n.NewState(), n.NewState(), n.NewState(), n.NewState()
s1.NewEdge(0, s2)
s1.NewEdge(Epsilon, s3)
s2.NewEdge(1, s2)
s2.NewEdge(1, s4)
s3.IsAccepting = true
s3.NewEdge(0, s4)
s3.NewEdge(Epsilon, s2)
s4.IsAccepting = true
s4.NewEdge(0, s3)
fmt.Printf("NFA\n%v\nDFA\n%v\nDFA with a dead state (as seen in the linked article)\n%v", n, n.Powerset(false), n.Powerset(true))
Output: NFA ->[0] ε -> [2] 0 -> [1] [1] 1 -> [1] [3] [[2]] ε -> [1] 0 -> [3] [[3]] 0 -> [2] DFA ->[[0]] 0 -> [1] 1 -> [1] [[1]] 0 -> [2] 1 -> [1] [[2]] 0 -> [3] 1 -> [1] [[3]] 0 -> [2] DFA with a dead state (as seen in the linked article) ->[[0]] 0 -> [1] 1 -> [1] [[1]] 0 -> [2] 1 -> [1] [[2]] 0 -> [3] 1 -> [1] [[3]] 0 -> [2] 1 -> [4] [4] 0 -> [4] 1 -> [4]
Example (Complexity) ¶
// Because the DFA states consist of sets of NFA states, an n-state NFA
// may be converted to a DFA with at most 2^n states. For every n,
// there exist n-state NFAs such that every subset of states is
// reachable from the initial subset, so that the converted DFA has
// exactly 2^n states. A simple example requiring nearly this many
// states is the language of strings over the alphabet {0,1} in which
// there are at least n characters, the nth from last of which is 1.
// It can be represented by an (n + 1)-state NFA, but it requires 2^n
// DFA states, one for each n-character suffix of the input. [9]
n := NewNFA()
// NFA for regexp `(0|1)*1(0|1)(0|1)`
s0, s1, s2, s3 := n.NewState(), n.NewState(), n.NewState(), n.NewState()
s0.NewEdge(0, s0)
s0.NewEdge(1, s0)
s0.NewEdge(1, s1)
s1.NewEdge(0, s2)
s1.NewEdge(1, s2)
s2.NewEdge(0, s3)
s2.NewEdge(1, s3)
s3.IsAccepting = true
fmt.Printf("NFA\n%v\nDFA (minimal)\n%v", n, n.Powerset(false))
Output: NFA ->[0] 0 -> [0] 1 -> [0] [1] [1] 0 -> [2] 1 -> [2] [2] 0 -> [3] 1 -> [3] [[3]] DFA (minimal) ->[0] 0 -> [0] 1 -> [1] [1] 0 -> [2] 1 -> [5] [2] 0 -> [3] 1 -> [4] [[3]] 0 -> [0] 1 -> [1] [[4]] 0 -> [2] 1 -> [5] [5] 0 -> [6] 1 -> [7] [[6]] 0 -> [3] 1 -> [4] [[7]] 0 -> [6] 1 -> [7]
func (*NFA) Reverse ¶
Reverse returns a NFA for the reverse language accepted by n.
Example ¶
// See http://en.wikipedia.org/wiki/Powerset_construction#Example
n := NewNFA()
s1, s2, s3, s4 := n.NewState(), n.NewState(), n.NewState(), n.NewState()
s1.NewEdge(0, s2)
s1.NewEdge(Epsilon, s3)
s2.NewEdge(1, s2)
s2.NewEdge(1, s4)
s3.IsAccepting = true
s3.NewEdge(0, s4)
s3.NewEdge(Epsilon, s2)
s4.IsAccepting = true
s4.NewEdge(0, s3)
fmt.Printf("NFA\n%v\nNFA reversed\n%v", n, n.Reverse())
Output: NFA ->[0] ε -> [2] 0 -> [1] [1] 1 -> [1] [3] [[2]] ε -> [1] 0 -> [3] [[3]] 0 -> [2] NFA reversed [[0]] [1] ε -> [2] 0 -> [0] 1 -> [1] [2] ε -> [0] 0 -> [3] [3] 0 -> [2] 1 -> [1] ->[4] ε -> [2] [3]
func (*NFA) SetStart ¶
SetStart sets the NFA's start state. Passing a state from a different NFA will panic.
type State ¶
type State struct {
IsAccepting bool // Whether this state is an accepting one.
// contains filtered or unexported fields
}
State is one of the NFA states.
func (*State) Closure ¶
Closure returns a state set consisting of s and all states reachable from s through ε edges, transitively.
func (*State) NewEdge ¶
NewEdge connects state s and state next by a new edge, labeled by sym. By convention, passing sym == Epsilon is reserved to indicate adding of an ε edge.
TODO implement priorities for sym < Epsilon
func (*State) Transitions ¶
func (s *State) Transitions() Transitions
Transitions returns the symbol -> closure projection of state s.
type Transitions ¶
type Transitions struct {
// contains filtered or unexported fields
}
Transitions maps symbols to their associated closures.
func NewTransitions ¶
func NewTransitions() Transitions
NewTransitions returns a newly created Transitions.
func (Transitions) Delete ¶
func (t Transitions) Delete(sym int)
Delete removes the closure associated with sym.
func (Transitions) Len ¶
func (t Transitions) Len() int
Len returns the number of edges in transitions.
Source Files