DFA: Deterministic Finite Automata

What is Deterministic Finite Automata

In theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite state machine—is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automation for each input string.[1] 'Deterministic' refers to the uniqueness of the computation. In search of simplest models to capture the finite state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automaton in 1943. (sited from here)

Output Transition Table

This package also can output transition table, which is a way to represent all transition function in this DFA.

dfa := NewDFA(0, false)
dfa.AddState(1, false)
dfa.AddState(2, true)

dfa.AddTransition(0, "a", 1)
dfa.AddTransition(1, "b", 2)

dfa.PrintTransitionTable()

// ===================================================
// 	     a|	 b|
// ---------------------------------------------------
// 0 |	 1|	NA|
// 1 |	NA|	 2|
// 2 |	NA|	NA|
// ---------------------------------------------------
// ===================================================

Installation and Usage

Install

go get github.com/kkdai/dfa

Usage

package main

import (
    "github.com/kkdai/dfa"
    "fmt"
)

func main() {
	dfa := NewDFA(0, false)
	dfa.AddState(1, false)
	dfa.AddState(2, true)

	dfa.AddTransition(0, "a", 1)
	dfa.AddTransition(1, "b", 2)

	var inputs []string
	inputs = append(inputs, "a")
	inputs = append(inputs, "b")
	fmt.Println("If input a, b will go to final?", dfa.VerifyInputs(inputs) )
}

Inspired By

• DFA: Wiki
• fffaraz/DFA
• Coursera: Automata

Project52

It is one of my project 52.

License

This package is licensed under MIT license. See LICENSE for details.