# Understanding definition of epsilon closure and finite automata states

I am going through the book , introduction to compiler design , by Torben Ægidius Mogensen.

It provides the following definition of an epsilon closure :

Given a set M of NFA states, we deﬁne $\ \epsilon$-closure($\ M$) to be the least (in terms of the subset relation) solution to the set equation $\ \epsilon$-closure($\ M$) =$\ M$ $\ \cup$ {$\ t$|$\ s$ ∈ $\ \epsilon$-closure($\ M$) and $\ s^\epsilon t$∈T}, where T is the set of transitions in the NFA.

Initially , it defined the notion $\ a^b c$ to mean that a transition from state $\ a$ to $\ b$ takes place when a symbol $\ c$ is encountered .

But in the above definition $\ s^\epsilon t$ , $\ t$ is an element of the set of transitions , not the set of states .

This has resulted in a bit of confusion as to what exactly does an epsilon closure mean .

One more terminology word-play that wanted to be clear about is , the exact meaning of a sentence of the following sort :

"We extend the set of NFA states with those you can reach from these by using only epsilon transitions ."

But in a set of NFA states , the epsilon transition would direct one state to another which would be already included in the set of NFA states. So , how is it possible to extend the same set with the elements already contained in it ?

• Can you transcribe the image into text? This will enable the search feature to access the text in the image. Oct 1, 2017 at 16:21
• @YuvalFilmus : Yes sure Oct 1, 2017 at 16:41

Your textbook is being very formal, probably since it aims at using set equations later on. However, $\epsilon$-closure is a very simple concept. The $\epsilon$-closure of a set $M$ of states is the collection of states that can be reached from a state in $M$ by taking any number of $\epsilon$-transitions (possibly zero).
The textbook uses a different (but equivalent) definition: it defines the $\epsilon$-closure of $M$ to be the smallest set of states that contains $M$ and that for every state $s$ that it contains, contains all states reachable from $s$ by a single $\epsilon$-transition.
Regarding the second quote, there is some context missing. Here is one possible context which would make sense. For an NFA without $\epsilon$-transitions, we define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$. When we have $\epsilon$-transitions, there are several different possible definitions of the transition function. One possibility is to define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$ and then an arbitrary number of transitions labeled $\epsilon$ (possibly none).
• The $\epsilon$-close of $M$ consists of all states you can reach from $M$ by taking zero or more $\epsilon$-transitions. Oct 1, 2017 at 16:20
• I added a paragraph with the meaning of the notation. In fact, $t$ is a single state. Oct 1, 2017 at 16:47