5
$\begingroup$

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 define $\ \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 ?

$\endgroup$
  • $\begingroup$ Can you transcribe the image into text? This will enable the search feature to access the text in the image. $\endgroup$ – Yuval Filmus Oct 1 '17 at 16:21
  • $\begingroup$ @YuvalFilmus : Yes sure $\endgroup$ – Eddie Dorphy Oct 1 '17 at 16:41
9
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ epsilon closure is a set of states which are always in M or may lie outside M ? $\endgroup$ – Eddie Dorphy Oct 1 '17 at 16:16
  • $\begingroup$ The $\epsilon$-close of $M$ consists of all states you can reach from $M$ by taking zero or more $\epsilon$-transitions. $\endgroup$ – Yuval Filmus Oct 1 '17 at 16:20
  • $\begingroup$ : So they may not be included in M , right ? $\endgroup$ – Eddie Dorphy Oct 1 '17 at 16:39
  • $\begingroup$ Any suggestions as to why in the defintion of e-closure has he termed "t" to be set of all transitions . As per the way the notation is understood shouldn't it be a set of states ? $\endgroup$ – Eddie Dorphy Oct 1 '17 at 16:41
  • $\begingroup$ I added a paragraph with the meaning of the notation. In fact, $t$ is a single state. $\endgroup$ – Yuval Filmus Oct 1 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.