# fas-js

1.3.1 • Public • Published

# Finite Automaton Simulator

Easily create and simulate state machines using this JS library. Import into your own server side or browser based JS application.

## Installation

Add the latest version of `fas-js` to your package.json:

``````npm install fas-js --save-dev
``````

Import the ES6 module:

``````var fas_js = require('fas-js');
``````

Import into HTML file

``````<script src="https://cdn.jsdelivr.net/npm/fas-js/lib/bundle.js"></script>
``````

## Background

A finite automaton is a formally defined state machine, a concept that can then be expanded on to build more complex and powerful computational machines. I highly recommend the book "Introduction to the Theory of Computation" by Michael Sipser if you want to learn more about FSAs and related concepts.

A Finite State Automaton (FSA) is defined as a 5-tuple (Q, Σ, δ, q0, F) where:

1. Q is a finite set called states
2. Σ is a finite set called alphabet
3. δ: Q x Σ → Q is the transition function
4. q0 ∈ Q is the start state
5. F ⊆ Q is the set of accept states

An FSA can be conceptualized as a Directed Graph, or more specifically, an Oriented Graph. It's often visualized in this way for teaching and demonstration purposes. It is also important to understand Sets and their logical operators when working with FSAs.

A Deterministic Finite Automaton (DFA) has exactly one transition for each symbol on every state. A Nondeterministic Finite Automaton (NFA) may have any number of transitions (including no transition) for an input symbol on any given state. NFAs may also include an ε-transition, a transition that occurs without consuming an input symbol. By definition, all DFAs are also NFAs. It also follows that all NFAs can be represented as a DFA.

## Creation

This library offers one method for creating an FSA. The parameters correspond to the definition above:

# createFSA(Q: string[], Σ: string | string[], δ: Object[], q0: string, F: string[]): FSA <>

### Inputs

Q cannot be empty, and each state name must be unique

Σ cannot be empty, and can be passed in as one string (each character will be interpreted as a separate symbol) or a string array. Cannot contain duplicate symbols. For NFAs, you do not need to specify the empty string, it is implicitly added.

δ is an array of objects that define the transitions between states. This object differs for DFAs and NFAs, and createFSA() will determine which to create based on the structure of this input.

• For DFA: `{from: "origin_state", to: "dest_state", input: "symbol"}`
• For NFA: `{from: "origin_state", to: "dest_state1,dest_state2,...", input: "symbol"}`

Input array for DFAs must contain a transition for each alphabet symbol on each origin state. Thus, the size of δ = size of Σ x size of Q. Σ cannot contain an empty string as a symbol for DFAs.

For NFAs, the `to` field can contain one or more destination states, comma separated, no spaces between state names. The `input` field can be `""`, indicating an ε (empty) transition.

q0 is the start state of the FSA. The first symbol of the input string is processed on this state. It must be a member of Q.

F is the set of accept states, which determine whether a given input string is "accepted" by the FSA or "rejected". This determination is made after the last symbol of the input has been read. If any of the final states are in the accepting set, that string is accepted.

The set of accept states must be a subset of Q - it can also be an empty set (an FSA that always rejects). For simulation purposes, F is passed in as a string array that cannot contain duplicate states

### Examples

# FSA
`createFSA()` returns an object with custom type. This object has no public properties, but does include helper methods available to the user.

getType(): string - returns either `"DFA"` or `"NFA"`

generateDigraph(): string - returns digraph according to DOT language to be used for visualization.

## Simulation

There are two simulation options available:

# simulateFSA(w: string | string[], fsa: FSA, logging: boolean = false, returnEndState: boolean = false) <>

Runs the entire input `w` through the `fsa`. `w` must only contain symbols from the alphabet defined in `fsa`. By default, the function returns a boolean signifying whether `w` was accepted by the `fsa`. If `returnEndState` is set to true, the function will instead return the final state (string) or the final array of states (string[]), depending on whether `fsa` is a DFA or NFA.

# stepOnceFSA(w: string, qin: string | string[], fsa: FSA, logging: boolean = false) <>

Returns the destination state(s), based on input symbol `w` and input state `qin`, as defined by δ of `fsa`. `w` must match a symbol from the alphabet defined in `fsa` (can also be the empty string). `qin` must be a state in Q. Use this function if you'd like to iterate through an input string step-by-step.

Note: In both functions above, a third `logging` parameter is available (defaults to false) which will print useful messages to the console as the simulator processes the input string. This can be used for debugging purposes or server-side logs. It is recommended to leave it defaulted to false for browser applications.

### Examples

Both simulators require an FSA object created with createFSA(). Here we will use the FSAs created in the Examples above.

## Demo

This library provides an engine that creates and simulates an FSA. The demo below provides a UI that utilizes this engine and visualizes the FSA as it's being processed. It's a great way to learn about FSAs and experiment with your own FSA creations! The UI and graph visualizations were built using preact, d3.js, and d3-graphviz.

## Package Sidebar

### Install

`npm i fas-js`

### Repository

github.com/jml6m/fas-js

2

1.3.1

GPL-3.0-or-later

119 kB

4