Theory

Non-Deterministic Finite Automata(NFA)

NFA (Non-Deterministic Finite Automata) is a state machine used to validate an input string using state transitions. In NFA, multiple paths can exist from the current state to the next state for an input symbol.

Regular Expressions

Regular expressions are a sequence of characters that are used to check if the given string follows the pattern or not.

There are two main methods for converting a given NFA to a regular expression:

1. State Elimination Method

2. Arden's Theorem Method

State elimination Method

Step -1

If there are incoming transitions to the initial state:

Create a new start state with no incoming edges.

Add an outgoing edge from the new start state to the old start state with an ε-transition.

The initial state before is now a normal state with an added incoming ε-transition.c

Step-2:

If there are outgoing transitions from the final state:

Create a new final state with no outgoing edges.

Add an incoming edge to the new final state from the old final state with an ε-transition.

The old final state is transformed into a normal state with the added transition of ε.

Step-3:

If the automaton has multiple final states:

Remove the final state status from the multiple final states.

Add outgoing ε-transitions from the multiple final states to a new and only final state with no outgoing transitions.

Step-4:

Eliminate all the states one by one except initial state and final state to get the final result which is the regular expression for the given NFA