Skip to content

w-i-l/deterministic-nondeterministic-finite-automata

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 

Repository files navigation

Deterministic & Nondeterministic Finite Automata

A program to determine acceptance of a word



About it

The purpose of this program is to determine whether a word is accepted by a given DFA or NFA.



How to use it

It has builtin a CLI with 3 options:

  • Read a DFA
  • Read a NFA
  • - Both of them open a window to select a text file that contains the graph for the automata.

  • Process a word - read from the STDIN a word and prints whether is it accepted or not.

The text format

The automata expects the input to have this specific format:

node_number _ is_final _ next_node _ letter _ ...

Where:

  • the node number - represents a positive integer for that specific node
  • Note that the node 0 will be always consider the starting node!
  • is_final - a boolean that marks if the node is a terminal one. This should be written as f for a final one and n for a non-terminal one.
  • next_node - represents a positive integer for the next node adjacent
  • letter - is the corresponding letter from the automata's alphabet(it could be also any symbol) that lies on the edge of the connection
  • The three dots marks that we can have any number of nodes linked to this node.

Every node along with its content should be written on a different line.

The program accepts non-completed automata, but must have all nodes declared at least.

Example

Suppose that we have this automata:

The input file for this would be:

0 n 0 1 1 0
1 f 2 0 0 1
2 n 3 2
3 f

But if we wanted a complete automata we would complete the edges with a -1 node that coresponds for the abort state.

0 n 0 1 1 0 -1 2
1 f 2 0 0 1 -1 2
2 n 3 2 -1 0 -1 1
3 f -1 0 -1 1 -1 2



How it works

The program simulates an automata behavior, taking one letter at a time and decides the next node.



Tech specs

It has implemented 2 main classes:

  • Node class - that represents a node in the automata's graph
  • FA class(stands for Finate Automata) - storing the component nodes

The DFA and NFA classes inherits from the FA and adds the main functionallity, validate_word method, which differs between them.

The word validation in a NFA is done by running a backtracking through all nondeterministic nodes, whereas in a DFA is a liniar lookup.

The adjacent nodes are stored as an array of indices that corresponds to the node.
Example:
0 coresponds to node 0, 1 to node 1, ...

The file selector is done using the tkinter module, the root windows is hidden.

Releases

No releases published

Packages

No packages published

Languages