State Diagram Generator

Thursday. April 23, 2020 - 2 mins

State Diagram Generator

See project on GitHub and deployed here 🌐.

This project has been created to display the deterministic finite state automata (DFA) or the Non-Deterministic Finite State Automata (NFA) of any given valid regular expression.

A deterministic automata along with it’s transmission table will be generated for the given regular expression and the user can also check whether any given string is recognized by that particular regular language.

Motivation

The first purpose of building this web application was to show to the user the synonymity of the regular expression, the finite state machine and the transition table and how they can be used to recognize the same language.

The application aims to provide the user with a visual representation for all valid regular expressions in the form of deterministic or nondeterministic automata as this helps the user (even me, the author) - better understand machines and their corresponding regular languages.

This also helps the user understand how to build finite state machines from regular expressions better. The instantaneous state transition diagram tool also shows the states and next states for all possible symbols. The regular expression parser and string checker tool can then be used to check strings against the regular expression and the finite state machine and this text box was added to provide the user with a way to parse and check presence of strings in any given language in linear time.

Another motivation behind this application was to provide a visual interface that clearly shows the difference between the deterministic and non-deterministic finite state automata for the same regular expression (same regular language) and this difference seen visually can help users learn better how different machines with different number of states and different transitions can represent the same language.

Another motivation of building this web application was to provide future developers an interface over the DotScript Language that can be used to create finite state automatas. This web application is open source and can be viewed and extended by other developers. Other developers can build on this application and further extend it by adding features such as support for push-down automata, compiling and lexical parsing directly using the textbox for string checking to compile entire projects in different languages.

Finite Automata

A finite automaton is a 5-tuple (Q, Σ, δ, q, F) where

Q is a finite set called the states
Σ is a finite set called the alphabet.
δ : Q × Σ → Q is the transition function.
q ∈ Q is the start state.
F ⊂ Q are the acceptance states.

Anish Sachdeva

DTU Undergrad '21