Introduction

Our program consists of two main parts, including the conversion of Nondeterministic Finite Automaton (NFA) to deterministic finite automaton (DFA) and also Reduction for minimizing the given input as much as possible.

NFA TO DFA algorithms

The NFA to DFA algorithm contains three major functions. The first function(access lambda)،finds all possible transitions using epsilon transition. The second function(lambdaremove)، removes epsilon transitions by merging the related states. The last function(repeatedremove)makes a new transition table using the old values. That table is considered the final output of the program, which will be shown to the user after turning into a JSON format.

Reduction algorithms

The reduction Algorithm has two separate sections. The first section is for removing inaccessible states using a function (RemoveInaccessibleStates), and the second is for finding equal states. This part contains three major functions. The first function, (createTransitionTable), is responsible for creating a transition table. The second function, (findEqualStates) is responsible for finding equal states from the transition table and removing equal, repeated states. The last function (standardTransitionTable) is responsible for building a new machine with survived states. The final output is converted to JSON format and ready to be sent to Front.

Screenshots

Api

Nfa To Dfa

localhost:8000/nfa-to-dfa/{json_format}

Input example

The first index of our json is the states name, and in each states, we set their connection and state status. For example, in state "q0" we have just one connection with "q1" by "a" and other connections like "b", "λ", and "c" are null, but we shouldn't remove them from our input json and the last value "state" show the status of our state and only get "start", "final", "normal" value.

{
   "q0":{
      "a":[
         "q1"
      ],
      "b":[
         
      ],
      "λ":[
         
      ],
      "state":[
         "start"
      ]
   },
   "q1":{
      "a":[
         
      ],
      "b":[
         "q2"
      ],
      "λ":[
         
      ],
      "state":[
         "normal"
      ]
   },
   "q2":{
      "a":[
         
      ],
      "b":[
         
      ],
      "λ":[
         "q2"
      ],
      "state":[
         "final"
      ]
   }
}

Output example

In output we only have one extra states status and its "TRAP" like state "2" and other value are like input value.

{
   "0":{
      "state":[
         "start"
      ],
      "a":[
         "1"
      ],
      "b":[
         "2"
      ]
   },
   "1":{
      "state":[
         "normal"
      ],
      "a":[
         "2"
      ],
      "b":[
         "3"
      ]
   },
   "2":{
      "state":[
         "TRAP"
      ],
      "a":[
         "2"
      ],
      "b":[
         "2"
      ]
   },
   "3":{
      "state":[
         "final"
      ],
      "a":[
         "2"
      ],
      "b":[
         "2"
      ]
   }
}

Errors

If send empty JSON we will see these errors:

{"status": null}

If send the DFA machine we will see these errors because the DFA machine didn't need to change DFA and the input machine should be NFA:

{"is_dfa": True}

Reduction

localhost:8000/reduction/{json_format}

All of the inputs and outputs in reduction are like NFA to DFA Api.

Errors

If send empty JSON we will see these errors:

{"status": null}

If send the NFA machine we will see this error because the reduction algorithm just gets DFA machine:

{"is_nfa": True}

How to use

• Click and drag new Connections from the orange div in each State, Each State supports up to 20 Connections.

• Click on a Connection to delete or rename it.

• Double-click on the black movable button to see the Clear, NTD, Red, and Help button.

• Right-click on the white page to see a menu of buttons.

• Click on a 'Nfa 2 Dfa' button to convert from Nfa to Dfa and Show it.

• Click on a 'Reduction' button to process a Reduction algorithm.

• RightClick on a State to delete, rename, Start, or Finalize it.

• Double-click on whitespace to add a new State.

How to run

To run this project follow below steps:

1. Install python3, pip in your system.
2. Clone this repository https://github.com/mohamadkhalaj/statemachine-app.git.
3. Run below commands:

pip install -r requirements.txt
python manage.py collectstatic 
python manage.py runserver

4. Open the following address http://localhost:8000/ in your browser.
5. enjoy :)

Team members

• Amirhossein Moosavi
• Ali Hassanzadeh
• Mohammadmahdi Khalaj
• Mohammad Noroozi
• Amirhossein Bayati