Theory

Non-Deterministic Finite Automata (NFA)

A Nondeterministic Finite Automaton (NFA) is a theoretical machine used in formal language theory to recognize regular languages. It is defined as a 5-tuple:

NFA = (Q, Σ, δ, q₀, F)

• Q → finite set of states
• Σ → finite input alphabet
• δ → transition function, δ: Q × (Σ ∪ {ε}) → 2^Q
• q₀ ∈ Q → initial state
• F ⊆ Q → set of accepting (final) states

In an NFA, multiple next states may exist for the same input, including ε-transitions. A string is accepted if at least one computation path leads from q₀ to a final state in F after consuming the entire input.

Regular Expressions

A Regular Expression (RE) is a symbolic representation used to describe a regular language. Regular expressions use operators such as:

• Union (|): choice (e.g., a|b → "a" or "b")
• Concatenation: sequence (e.g., ab → "a" followed by "b")
• Kleene Star (*): repetition (e.g., a* → "", "a", "aa", …)

Every regular expression corresponds to an NFA, and every NFA can be converted into an equivalent RE. In this experiment, we apply the State Elimination Method.

State Elimination Method

The State Elimination Method converts an NFA into an equivalent RE by systematically removing states while preserving the accepted language. When only the start state and a final state remain, the label on the direct edge between them represents the final RE.

Algorithm

1. Standardize the NFA:
   • If the start state has incoming transitions, create a new start state with an ε-transition to the old start state.
   • If there are multiple final states, create a new final state and connect all old final states to it using ε-transitions.
2. Elimination of states (core step):

   For each intermediate state R (not start or final):

   • Let P = set of predecessor states of R.
   • Let S = set of successor states of R.
   • For every (p, R) and (R, s) path:
     • If there is a loop on R labeled r_RR, include (r_RR)*.
     • Update the transition from p → s as:

       r_ps = r_ps | (r_pR(r_RR)*r_Rs)

       (where r_ps is the existing label on edge p→s).
   • Remove state R from the automaton.
3. Repeat until only the start state and final state remain.
4. Final Expression:

   The label on the edge from the start state to the final state is the required Regular Expression.

Illustration

For example, consider an NFA with states Q = {q0, q1, q2}, where q0 is the start state and q2 is the final state. By applying elimination to q1, we rewrite transitions and finally obtain the RE for the language accepted by the automaton.