yalperg / otomat Goto Github PK

A library for converting Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).

License: MIT License

JavaScript 1.52% TypeScript 98.48%

otomat's Introduction

Otomat

Otomat is a TypeScript library for working with Finite State Automata (FSA), specifically for converting Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).

Installation

To install the library, use npm or yarn:

npm install otomat
pnpm add otomat

Usage

Here’s a basic example of how to create an NFA, convert it to a DFA, and interact with the automaton:

import { NFA, State, Transition, Alphabet } from "otomat";

// Define states
const q1: State = "q1";
const q2: State = "q2";
const q3: State = "q3";
const q4: State = "q4";

// Define alphabet
const alphabet: Alphabet = ["a", "b"];

// Define transitions
const transitions: Transition[] = [
  { from: q1, to: q2, symbol: "a" },
  { from: q1, to: q4, symbol: "a" },
  { from: q2, to: q2, symbol: "a" },
  { from: q2, to: q3, symbol: "a" },
  { from: q3, to: q3, symbol: "a" },
  { from: q3, to: q3, symbol: "b" },
  { from: q3, to: q4, symbol: "b" },
  { from: q4, to: q4, symbol: "a" },
];

// Create NFA
const nfa = new NFA([q1, q2, q3, q4], transitions, q1, [q4], alphabet);

// Convert NFA to DFA
const dfa = nfa.toDFA();

Using AutomataCreator to create an FSA from JSON

You can create an FSA (either DFA or NFA) directly from a JSON representation using the AutomataCreator:

import { AutomataCreator, FSAJSON } from "otomat";

// Define a JSON representation of an NFA
const nfaJson: FSAJSON = {
  states: ["q0", "q1"],
  transitions: [
    { from: "q0", to: "q1", symbol: "a" },
    { from: "q1", to: "q0", symbol: "b" },
    { from: "q0", to: "q0", symbol: "ε" },
  ],
  startState: "q0",
  acceptStates: ["q1"],
  alphabet: ["a", "b"],
};

// Create an NFA or DFA based on the JSON structure
const automaton = AutomataCreator.createFromJSON(nfaJson);

Architecture Diagram

The following UML diagram illustrates the architecture of the library:

Contributing

Contributions are welcome! Please feel free to submit a Pull Request or open an issue on GitHub.

otomat's People

Contributors

Watchers

otomat's Issues

Implement Caching Mechanism for epsilonClosure Method in NFA

Extract `EMPTY_STATE` and `EPSILON_SYMBOL` to Constants

Description:

Currently, the empty state (∅) and epsilon (ε) symbols are used directly within the codebase, particularly in the DFA and NFA classes. This approach can lead to inconsistencies and potential errors due to manual repetition. It also makes the code less maintainable if we ever need to change these symbols.

Proposal:

Extract the empty state (∅) and epsilon (ε) symbols into constants, such as EMPTY_STATE and EPSILON_SYMBOL, which will be defined in a dedicated constants.ts file. These constants should then be imported and used wherever these symbols are required.

toDFA Method Doesn't Generate All Possible States When removeUnreachableStates is False

When converting an NFA to a DFA using the toDFA method, setting the removeUnreachableStates parameter to false is supposed to generate all possible states, including those unreachable from the initial state. However, currently, the toDFA method does not generate these unreachable states.

This issue did not exist before the recent refactor of the toDFA method, where the method was broken down into smaller functions. It seems that during the refactor, the generation of all possible states, including unreachable ones, was not handled correctly.

Steps to Reproduce:

Create an NFA with multiple states, some of which are not reachable from the initial state.
Convert the NFA to a DFA using toDFA (removeUnreachableStates: false).
Observe that the resulting DFA does not include the unreachable states from the initial state.

Expected Behavior:

When removeUnreachableStates is set to false, the toDFA method should generate a DFA that includes all possible states (i.e., all subsets of the NFA's states), even if some of those states are unreachable from the initial state.

Actual Behavior:

The toDFA method currently only includes states that are reachable from the initial state, even when removeUnreachableStates is false.

Implement Caching Mechanism for toDFA Method in NFA

Description:

The toDFA method in the NFA class currently converts the NFA to a DFA every time the method is called, even if the NFA has not changed. This can lead to unnecessary recomputations, especially in scenarios where the conversion is called frequently without any modifications to the NFA.

Proposal:

Introduce a caching mechanism in the NFA class to store the result of the toDFA method. The method should only recompute the DFA if the NFA has been modified since the last conversion. If the NFA is unchanged, the cached DFA should be returned.

Suggested Implementation:

Add a private variable cachedDFA in the NFA class to store the cached DFA.
Modify the toDFA method to check if the cachedDFA exists and return it if available.
Reset the cache (cachedDFA = null) whenever the NFA is modified (e.g., when states or transitions are added, or the start state is changed).