/Finite-Automata-Machine

Regex -> ε-NFA -> DFA -> minDFA, lexical analysis

Primary LanguagePython

Finite-Automata-Machine

Overview

This is a python program to construct ε-NFA, DFA, and minimised DFA from a given regex. After constructing DFA, it can judge a given word whether it matches the regex.

Requirements

  • Python 3
  • python-graphviz

Install

git clone https://github.com/YanhuiJessica/Finite-Automata-Machine.git
cd Finite-Automata-Machine/
pip3 install -r requirements.txt
python3 lexical_analysis.py

Regex -> NFA

  • Regex2NFA.basicstruct
    basic struct
  • Regex2NFA.linestruct
    line struct
  • Regex2NFA.dotstruct
    dot struct
  • Regex2NFA.starstruct
    star struct

Sample Generation

  • Sample regex: 1*0(0|1)*
  • Sample-generated NFA:
    Sample-generated NFA
  • Sample-generated DFA:
    Sample-generated DFA
  • Sample-generated minDFA:
    Sample-generated minDFA