Repository files navigation

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.

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

An alias for state identifiers.

An alias for input symbols.

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

The set of destination states for a given transition.

dataNFA=NFA{initState::State,currentStates::SetState,totalStates::SetState,finalStates::SetState,transitions::MapTransitionInputDestStates,inputAlphabet::SetSymbol}

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

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

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

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

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

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

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

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

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

According toKleene’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)