jvzmarmentini / automaton-app Goto Github PK

An application that converts a finite non-deterministic automaton into a finite deterministic automaton and process a given word

Create a program that, given an finite deterministic automaton M, defined in a text file, execute the following operations:

• Convert a non-deterministic automaton into an equivalent finite deterministic automaton;
• Allow the user to give a word to be recognized by the deterministic automaton;
• The program should determinate if the word received is accepted by the automaton;

• The program from item 1 should be implemented using any programming language;
• The entry file format containing the non-deterministic automaton definition must follow the following pattern (including spaces between words):

<M>=({<q0>,...,<qn>},{<s1>,...,<sn>},<ini>,{ <f0>,...,<fn>})

Prog

(<q0>,<s1>)=<q1> ... (<qn>,<sn>)=<q0>

Where: <M> is the automaton name; <qi> represents one state of the automaton for 0 ≤ i ≤ n, com n ∈ N e n ≥ 0; <si> represents one symbol of the alphabet of the language recognized by the automaton for 1 ≤ i ≤ n, com n ∈ N e n ≥1; <ini> indicates the initial state of the automaton, where ini is a state of the automaton; <fi> represents one final state of the automaton where ini is a state of the automaton and 0 ≤ i ≤ n, com n ∈ N e n ≥ 0; (<qi>,<si>)=<qj> describes the function applied to a state <qi> and a <si> entry symbol that leads to the computation to a state <qj>.

Example: AUTÔMATO=({q0,q1,q3,q4,q5,q7,q8},{L,S,I,P,C,E},q0,{q7})

Prog

(q0,S)=q4 (q0,L)=q1 (q0,L)=q3 (q1,I)=q7 (q3,P)=q5 (q4,E)=q7 (q8,I)=q7 (q5,I)=q7 (q3,C)=q8

• Python
• NetworkX
• PyGraphviz

Install python 3 and download the project files.

The initial requisites is to have Python installed in your machine. Here's where you can get it:

• Download Python

We strongly recommend using linux or macOs.

1. Clone the repo

   git clone https://github.com/jvzmarmentini/automaton-app.git

2. Install NetworkX package

   pip install networkx

3. Install PyGraphviz package

• 3.1. Linux (ubuntu or debian)

  sudo apt install graphviz graphviz-dev
  pip install pygraphviz

• 3.2. macOs - Homebrew

  brew install graphviz
  pip install pygraphviz

• 3.3. Windows https://pygraphviz.github.io/documentation/stable/install.html#windows

Before executing the application, be sure that the automato.txt file has a state machine and it is formated.

To run, use:

python3 main.py automaton-file word

Then, the generated state machine will be drawn in a png file and the result (if the word is accepted) will be printed.