Skip to content

Latest commit

 

History

History
32 lines (23 loc) · 1.74 KB

README.md

File metadata and controls

32 lines (23 loc) · 1.74 KB

main

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

trie

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