Trie & DAWG visualizer

A simple trie and dawg visualizer using GraphViz in TS

Webpage: keivan-sf.github.io/dafsa-visualizer

Motivation

I don't have experience in theories of computation so one should not look at this project as the right way of implementing these data structures. The main goal is to help visual learners like me understand the concepts of them.

How it works

The program first builds a Trie and them performs a DFA minimization to convert it into a DAWG.

As far as I know, there are 2 ways of creating a DAFSA/DAWG:

• Creating a trie then minimizing it
• Creating a dawg in one step

Examples

Resources

Article and projects which I find useful in this concept:

Wiki pedia - DAFSA

JB's Blog - DAWG

Incremental Construction of Minimal Acyclic Finite State Automata and Transducers

• This article shows a way of creating a dawg in one step

Github.com/vtortola/dawg

• This repo implements a dawg building algorithm in c# and contains a visual explanation of it along side useful data and statistics

DFA-minimization algorithm

• This video explains a DFA-minimization algorithm along side other useful concepts. Which can be used in minimizing a trie into a dawg