NFA.hs - Nondeterministic Finite Automaton in Haskell

This module implements a Nondeterministic Finite Automaton (NFA) in Haskell, following the concepts of automata theory and based on Kleene’s Theorem, which asserts the equivalence of regular expressions and NFAs.

📚 Overview

An NFA is a computational model used to recognize regular languages. This implementation supports:

• Creation of an NFA with states and transitions
• Input simulation and state transitions
• Final state verification
• Transition table printing

🔧 Data Types

type State = Int

An alias for state identifiers.

type Symbol = String

An alias for input symbols.

type TransitionInput = (State, Symbol)

Defines the key for the transition function: a state and an input symbol.

type DestStates = Set State

The set of destination states for a given transition.

data NFA

data NFA = NFA {
    initState     :: State,
    currentStates :: Set State,
    totalStates   :: Set State,
    finalStates   :: Set State,
    transitions   :: Map TransitionInput DestStates,
    inputAlphabet :: Set Symbol
}

📦 NFA Structure

Represents the NFA structure with:

• initState: The starting state
• currentStates: The current active states
• totalStates: All defined states
• finalStates: The set of accepting states
• transitions: A map of transitions
• inputAlphabet: All used input symbols

---

🛠️ Functions

newNFA :: State -> Bool -> NFA

Creates a new NFA with an initial state. Optionally marks it as final.

addState :: State -> Bool -> NFA -> NFA

Adds a new state to the NFA and optionally marks it as final. Ignores the dead state -1.

addTransition :: State -> Symbol -> [State] -> NFA -> NFA

Adds a transition from a source state to a list of destination states on a given input symbol.

inputSymbol :: Symbol -> NFA -> NFA

Consumes an input symbol and updates the current active states based on the transition function.

verify :: NFA -> Bool

Checks whether any of the current states is a final state (i.e., the input string is accepted so far).

resetNFA :: NFA -> NFA

Resets the NFA to its initial state. All transitions and states remain unchanged.

verifyInputs :: [Symbol] -> NFA -> Bool

Simulates the NFA over a sequence of input symbols and returns True if the final state is accepting.

printTransitionTable :: NFA -> IO ()

Prints the transition table to the console in a readable format.

---

🧠 Theoretical Context

According to Kleene’s Theorem, regular expressions, DFAs, and NFAs are equivalent in expressive power. This implementation enables one to:

• Construct an NFA from state/transition rules
• Evaluate input sequences
• Eventually transform the NFA into a regular expression (GNFA-based algorithms not included here)