Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is the epsilon NFA?

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

An epsilon nondeterministic finite automaton (NFA) has null or epsilon transitions from one state to another. Epsilon NFA is also called a null NFA or an NFA lambda.

A regular expression for a language forms an epsilon NFA. This epsilon NFA then converts to a simple NFA. We then use the simple NFA to make a deterministic finite automaton (DFA).

Null closure

We require null closure to convert an epsilon NFA to an NFA. Moreover, it shows us the states we can transcend due to a null transition.

Note: We can visit here to learn how to convert an epsilon NFA to NFA.

Let's suppose an NFA <Q,Σ,q0,δ,F><Q, Σ, q0_​, δ, F> and SQS \subseteq Q is a defined set of states, where:

  • QQ is the finite set of states
  • ΣΣ is the input symbols
  • q0q_0 is the start state
  • δδ is the transition function
  • FF is the final state

The null closure of SS is the set Λ(S)Λ(S). We can define it recursively as follows:

  1. SΛ(S)S \subseteq Λ(S)
  2. For every qΛ(S)q \in Λ(S), δ(q,Λ)Λ(S)δ(q, Λ) \subseteq Λ(S)

Example

Consider the following epsilon NFA, where q0q_0 is the start state.

g ENTRY q0 q0 ENTRY->q0 q3 q3 q3->q3   0 q0->q0   0 q1 q1 q0->q1   Λ q1->q3   Λ q2 q2 q1->q2   0 q2->q1   1
An epsilon NFA

The null closure of the NFA is as follows:

Null closure

State

Set

q0

{q0, q1, q3}

q1

{q1, q3}

q2

{q2}

q3

{q3}

We determine this null closure by how a transition transcends from one state to another with a null input.

RELATED TAGS

CONTRIBUTOR

Ayesha Kanwal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring