fsa.go

package fsa

type FSA interface {
	Accept(s string) bool
}

nfa.go

package fsa

import (
	"fmt"
	"os"
	)

const (
	BUFFSIZE = 10
)

type err struct {
	error string
}

func (b err) String() string {
	return b.error
}


type NFA struct {
	numStates int
	start int
	delta []map[byte][]int
	final []bool
	epsilon byte
}

func NewNFA(numStates, q0 int, delta []map[byte][]int, F []int, epsilon byte) (*NFA, os.Error) {

	if numStates < 1 {
		return nil, err{fmt.Sprintf("Error: Invalid number of states specified: %v", numStates)}
	}

	if len(delta) != numStates {
		return nil, err{fmt.Sprintf("Error: NewNFA called with numStates = %v, but delta defined for %v states", numStates, len(delta))}
	}

	if 0 > q0 ||  q0 >= numStates {
		return nil, err{fmt.Sprintf("Error: Invalid initial state specified: %v", q0)}
	}

	//Make final state lookups a bit easier
	final := make([]bool, numStates)
	for _, q := range F {
		if q < 0 || q >= numStates {
			return nil, err{fmt.Sprintf("Error: Illegal final state %v specified, should be between 0 and %v", q, numStates - 1)}
		}

		final[q] = true
	}

	return &NFA{numStates, q0, delta, final, epsilon}, nil
}


//TODO: Control chan w/ select statements
func (this *NFA) Accepts(input string) bool {
	var running bool = true //Flag to stop execution of states

	//Setup control chans
	out := make(chan bool)
	accept := make(chan bool)
	halt := make(chan int, this.numStates)
	counter := make(chan int, BUFFSIZE * this.numStates)

	//Setup transition chans
	states := make([]chan string, this.numStates)
	for i := range states {
		states[i] = make(chan string, BUFFSIZE)
	}
	
	//call monitor
	go func() {
		var active int = 1 //Number of inputs alive in system
		var accepted bool = false //
		
		for {
			accepted, _ = <-accept //Check for acceptance
                        active += <-counter//TODO: Examine: Can we ever hang here?

			//If accepting path found, or no more input is waiting in a buffer
			if accepted || active == 0 {
				out <- accepted; //Alert the media!
				
				//Then clean up:
				running = false; //Stop state execution
				
				//States may all be blocking, free them
				for i := 0; i < this.numStates; i++ {
					halt <- 1
				}

				return
			}
		}
	}()
	
	//call states
	for i := range states {
		go func(label int) {
			var in string

			for running {
				select {
				case <-halt : return
				case in = <-states[label] :

					if len(in) != 0 {
						for _, c := range this.delta[label][in[0]] {
							states[c] <- in[1:]
							counter <- 1
						}
					}
					
					for _, c := range this.delta[label][this.epsilon] {
						states[c] <- in
						counter <- 1
					}
					
					counter <- -1
				}
			}
			
		}(i)
	}

	//push input..
	states[this.start] <- input

	//..and wait
	return <-out
}

testNFA.go

package main

import (
	"fmt"
	"os"
	"./fsa"
	)

func main() {
	EvenOr1, err := fsa.NewNFA(5, 0, []map[byte][]int{
		map[byte][]int{'E' : []int{1,3}} //delta for q0
		map[byte][]int{'1' : []int{2}} //q1
		map[byte][]int{} //q2
		map[byte][]int{'0' : []int{4}, '1' : []int{4}} //q3
		map[byte][]int{'0' : []int{3}, '1' : []int{3}} //q4
	}, []int{2,4}, 'E')

	if err != nil {
		fmt.Println(err.String())
		return
	}

	for {
		//get str
		//accept
	}