A program which takes an input file and encodes an automaton for testing of a Finite State Machine
This struct holds information of a 5-Tuple:
// Automaton is a 3-Tuple representing a deterministic finite automaton.
type Automaton struct {
StartState int
AcceptStates []int
TransitionFunction map[rune][]int
}
-
$Q$ : The set of states, is implied by the length of the slice[]int
which maps an input for each state to an output state. -
$Σ$ : The alphabet, is implied by therune
which maps inputs to the output state. -
$δ$ : The transition function, is specified by theTransitionFunction
directly.$δ : Q \times Σ \rightarrow Q, \ \ \forall\ q \in Q, \ \ \forall\ l \in Σ$ that is to say, that for every state,$δ$ maps each letter of the alphabet to a new state. -
$q_0$ : The start state of the automaton, is specified by the integerStartState
. In this implementation,$q_0 \in [1, n]$ , where$n$ is the number of states. -
$F$ : The set of accept states, is specified by the integer sliceAcceptStates
.$q \in [1, n],\ \ \forall\ q \in F$ these specify the final states in which a word composed of input symbols from$Σ$ are accepted in.
The Automaton
struct implements a method Recognize(word string) bool
. This method returns true
if the given word is recognized by the language the automaton specifies.
To represent an automaton in a more human readable form, this package supplies a function EncodeAutomaton(inStream []byte) (*Automaton, error)
to encode a finite deterministic automaton into Go based on byte stream input from a .yaml
file.
# Yaml file for a 4-tuple description of a finite automaton (alphabet is infered from the transition function)
# Deterministic Finite Automaton which encodes the regular expression (-|+)?[0-9]+
states: 4
initial: 1
finalstates: [3]
transitions:
- input: "-+"
outputs: [2,4,4,4]
- input: "0123456789"
outputs: [3,3,3,4]
states
Integer
- Defines the number of states
$n$ in the automaton.$Q : [1, n]$
initial
Integer
- Defines the initial state
$q_0$ of the automaton.
finalstates
List of Integer
- Defines the set of states
$F$ which the automaton accepts.
transitions
List of Map
- The list of transitions which defines the transition function
$δ$ .
transitions.transition
Map
- A transition which maps all input symbols in
$Σ$ to the set of all states$Q$ .
transition.input
String
- The input string maps all symbols in the string to the set of outputs.
transition.outputs
List of Integer
- The set of output states in
$Q$ where the input state is defined by the index of the list.
The binary file generated by this program is a very basic User Interface which allows a user to input an automaton and test words which the automaton may recognize.
The path of a .yaml
file specifying an automaton must be passed as an argument to the binary file. The program will then validate that that .yaml
file correctly specifies an automaton, and proceed to query the user for words and outputting whether or not the automaton recognizes that word.