Automatons

Automaton's Algorithms implemented in Java.

Tip

Project Documentation

Class Notes

• Feature Wishlist
• Installation
• Usage
  • Creating Automatons
  • Automaton Operations
  • De/Serializing Automatons
  • Automaton Machines

Feature Wishlist

Functionalities	Done	Tested
NFA to DFA	X	X
NFA-ε to DFA	X	X
Remove Unreachable States	X
ε-Closure	X
Minimize - Equivalency Method
Minimize - Table Method
Equivalency	X	X
Completion	X	X
Complement	X	X
Concatenation	X	X
Intersection	X	X
Union	X	X
Reversion	X	X
Language to NFA
Reg. Expr. to DFA
Reg. Expr. to NFA
Reg. Expr. to NFA-ε
Automaton to Json	X
Automaton Machine
Step by Step Algorithm

Installation

Maven

Paste the following dependency on your project's pom.xml file:

<dependency>
    <groupId>io.github.lcs002</groupId>
    <artifactId>automatons</artifactId>
    <version>0.0.2</version>
</dependency>

Note

For other version visit the Maven Central Repository.

Usage

Creating Automatons

First we must use an Automaton.Builder:

Automaton.Builder builder = new Automaton.Builder();

Then, we can set its Alphabet by using setAlphabet:

builder.setAlphabet(Set.of('a', 'b'));

Warning

Be sure the Alphabet is set before building the automaton.

Transitions are added by using addTransition with the source state, destination state and symbol as parameters:

// For normal transitions
builder.addTransition("q0", "q1", 'a');

// For epsilon transitions
builder.addTransition("q0", "q1", Automata.EPSILON);

Warning

All entries must be symbols from the automaton's alphabet.

Initial State is set by using setInitialState with the name of the state as parameter:

builder.setInitialState("q0");

Warning

Be sure the Initial State is set before building the automaton.

Final States are added by using addFinalState with the name of the state as parameter:

builder.addFinalState("q1");

Warning

Be sure at least one Final State is set before building the automaton.

Finally, you can create the configured Automaton by calling build():

Automaton automaton = builder.build();

Tip

You can visualize the automaton by simply printing it or using the method toString().

System.out.println(automaton);

Automaton Operations

Once the Automaton is created, you can perform operations on it, such as:

automaton = automaton.nfaToDfa();
automaton = automaton.complete();
automaton = automaton.reverse();

De/Serializing Automatons

To convert an Automaton to a JSON string, call the method serialize from the class AutomatonJsonSerializer:

String json = new AutomatonJsonSerializer().serialize(automaton);

To convert a JSON string to an Automaton, call the method deserialize from the class AutomatonJsonDeserializer:

Automaton automaton = new AutomatonJsonDeserializer().deserialize(json);

Automaton Machines

Automaton Machines make automatons functional, allowing to consume input and update its state according to the transitions.

To create an Automaton Machine, call the constructor of the class AutomatonMachine passing the automaton as parameter:

AutomatonMachine machine = new AutomatonMachine(automaton);

Warning

Be sure the automaton is valid, meaning it has at least one initial state and one final state. The provided automaton must be a DFA and also be complete.

To consume input, call the method consume passing the input as parameter:

// The input can be a single entry
String nextState = machine.consume('a');

// Or a sequence of entries
String nextState = machine.consume("abba");