Finite state machines

• 

  DFA

• 

  NFA

Inspiration

Currently in the theory of computation course, learning about automata (DFA, NFA) and regular languages. I wanted some program that can accept or reject input strings and simulate finite state machines. This project may help others who need to visualize DFAs and NFAs in a different representation.

What it does

Create your own DFA or NFA and run it by passing an input string. It outputs the path it takes per input symbol of the string and if the string is accepted or rejected by the machine.

How we built it

With Python.

Accomplishments that we're proud of

Building a program that simulates DFAs and NFAs.

What we learned

Finite state machines have a limited amount of memory (restricted to regular languages only). The main idea of the theory of computation is to know if the problem is solvable. Decidable problems are split into categories (Chomsky Hierarchy) and each grammar/language have their own characteristics.

What's next for Finite state machines

• Might try to do pushdown automata.
• Maybe add an option for regex

Built With

• python