Problem understanding DFA & NFA equivalence in Theory of Computation

Question

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction

but my question is a bit different from that. I was reading Michael Sipser's Introduction to Theory of Computation and I came to a problem. I couldn't understand as to how he is taking his act on equivalence between NFA and DFA.

I have problem understanding this para :-

Next, we determine the start and accept states of D. The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself. An ε arrow goes from 1 to 3, so E({1}) = {1, 3}. The new accept states are those containing N4’s accept state; thus {1}, {1,2}, {1,3}, {1,2,3}.

My assumption---> As {2} is not in the list of accepted states,so {1,2} should not be considered as new accept state in equivalent DFA.Also,{1} and {1,2,3} and {1,3} stand out as new accept states as per me because traversing from 1 to reasonable nodes lets the final accept state be reached---here,{1},accept state--->{1,3}---accept state as on inputting a from node 3 makes arrive at {1} which is an accept state,hence accpeted,and similarly for {1,2,3}.

So,point at my wrong thinking PLEASE. I have understood that while making transitions only those states are considered final states which are accept states in NFA.Am I wrong???So,how come {1,2} be the new accept state in the equivalent DFA?

Secondly, why he has mentioned that

The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself`.

I couldn't derive a meaning out of this statement,the reason might be my poor understanding of English language(I am non-native English speaker).Means start state is E({1})---fine upto here. Now, the set of states that are reachable from 1 by travelling along ε arrows,plus 1 itself---It doesn't make any meaning standing as an independent sentence. Someone make me understand the meaning of this line,PLEASE!

Someone please make me understand and elaborate a bit. I feel that author might be wrong there,pardon my noobiness or for any mistake!

Answer 1

Motivation. In this construction, the intent is to make a DFA equivalent to a given NFA. In the original NFA, look at what happens when we're in state 2 and we see input $a$: we could either stay in state 2 or make a transition to state 3. If we want to eliminate nondeterminism, we could say that from state 2 looking at input $a$ we move to the single new state $\{2,3\}$, meaning that in this case, we're either in state 2 or state 3. In other words, in the constructed DFA we'll have the transition $\delta'(\{2\}, a)=\{2, 3\}$. The important thing to notice is that this transition in the new FA is deterministic: from the state $\{2\}$ on reading $a$ we move to the single state denoted by $\{2, 3\}$. Guided by this convention, we will build the DFA by defining the states to be all possible sets over 1, 2, 3, namely $$ \emptyset, \{1\}, \{2\},\{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} $$

Final States. Let's start with an example: what does the NFA do on input $baa$? We'll have, in order

1. In state 1, looking at $b$. Go to state 2.
2. In state 2, looking at $a$. Go to state 2 or state 3.
3. Looking at the last input, $a$ we could be in either state 2 or state 3. If we're in state 2, go to state 2 or state 3 as before. If we're in state 3, go to state 1.

In other words, at this stage, after having read $baa$ we could find ourself in states 2, 3, or 1.

In the DFA, we have, equivalently, the transitions $\delta'$ defined as

1. $\delta'(\{1\}, b) = \{2\}$.
2. $\delta'(\{2\},a) = \{2, 3\}$.
3. $\delta'(\{2, 3\}, a) = \delta'(\{2\},a)\cup\delta'(\{3\},a) = \{2, 3\}\cup\{1\}=\{1, 2, 3\}$.

Now the question is, should state $\{1, 2, 3\}$ be considered as a final state? Sure, since the NFA, reading $baa$ has at lest one possible collection of transitions that leads to the accepting state 1. In a similar way, any state of the DFA containing 1 will be a final state, so in the DFA there will be four final states: $$ \{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\} $$ Now it turns out that in the DFA the state $\{1,2\}$ is never used, but that doesn't negate the fact that it's a final state (since it contains 1). All it means is that there is no transition that takes you there. It's what we call an unreachable state. This, I hope, answers your first question.

Start State. This answer to your first question has little to do with the answer to your second question. The answer for your second question is: just as we did to determine the final states of $D$, we also need to know what the start state of $D$ is, and in this case it will be the set of states containing the start state of $N_4$, along with any other states that can be reached from that start state via $\epsilon$-moves, namely $\{1, 3\}$ (which of course will also be a final state, though that's not important here).

Answer 2

Your question is unprecise. Yous state that you have a problem understanding some parts of the text, but without any further hint as to the nature of the problem.

You should be more specific about what is bothering you in this construction of the DFA $D$. For example, what do you think is wrong with the start state of $D$ being the set $\{1,3\}$. Is it the fact that it is a set of states, or the fact that it is this specific set of states $\{1,3\}$?

I suspect it may be the former, so I will try to answer that. I do not have Sipser's book, so that I cannot relate specifically to his presentation, other than with the page you give.

The major point in this is that state names do not matter. In the example, the names of the initial NFA $N_4$ are the integers $1$, $2$ and $3$. Now, you might wonder whether it is actually the first three natural integers, or only the three characters that represent them (or even, possibly, three strings of one character each). The fact is that it is irrelevant, that it does not matter. All you really need to describe/define your automaton is to have 3 distinct states, and to be able to distinguish them in some way so that you can tell where you start, how you can pass from one to another on some input, and which is accepting.

As usual, when you talk about something, the best way is to identify it with a name, which should refer to it only in a given context. It can be "babou" right now if I am the something. It can be the character "3" or the string "III" if it is the third natural integer, though you can also call it "third natural interger" which people will understand, or it can be the name "Joe" if you have first given the notational definition:

      Let Joe be a name for the third natural integer.

or more accurately

      Let "Joe" be a name for the third natural integer.

Though the quotes are needed only in the definition, since the beginning of this definition is about the name, rather than what is being named, quotes are not to be used when the name stands for what is being named. The name of Mary is "Mary", and "dogs" never bites (the "s" ending "bites" is intentional) while dogs may bite.

You can play a lot with names, which is sometimes very convenient. In particular, there is no reasons that names should be only spoken utterances, or written character strings. It works as well if you take names from any set, such as integers, or sets of integers for example.

Since other things, such as integers or sets of integers, need to be named too to talk about them, it is hard to know whether you are using themselves or their names when the names is written down. We have seen that there are notational devices to make the distinction when it is important (using quotes, for example), but you can often forget about it.

So here $1$, $2$, and $3$ are the names of the states. We now see that whether they stand for the character or the integer does not actually matter muuch.

If you take a DFA and change consistently the name of a state of the initial NFA $N_4$, but you might describe the same NFA with the names $9$, $8$, and $7$, or with $26$, $3$ and $15$, or with $1$, $2$ and $3$ assigned differently to the states so that the start state would now be $2$ (in the picture, you move $1$, $2$ and $3$, but you do not touch the start arrow or any other part of the picture), or it could even be the names Huey, Dewey, and Louie, or the names "foo", $2$ and "blue" (which is very useful if you describe the NFA with a poem).

In other words, in languages and automata theory, when you talk of a set of states or symbols, you can take any set of mathematical objects that you can enumerate (give me some time to think about sets that are countable but not recursively enumerable ... but this is no worry of yours). They do not even need to come from a consistent source. You only want them as names in order to describe and run you automaton.

But this should not encourage you to use strange naming. This naming freedom should rather be used to make things easier to understand and remember. This is probably why Sipser used $1$ for the start state.

You have exactly the same situation in programming, when you have to choose names/identifiers for variables, functions, classes or other entities, though these names are usually restricted to alphanumeric strings. Good programming practice recommands the use of identifiers that are meaningful, and help understand the program.

When building the DFA $D$, you can use any name you want for the states of $D$. However, it is convenient to use sets of names used for the states of the NFA $N_4$. This is usually simplified into saying that each state of $D$ is a subset of the states of $N_4$.

This choice of names is convenient, and helps understanding, because because a state of $D$ is intended to mimic (in some precise sense) the behavior of several states of $N_4$, precisely those it contains.

A complementary or alternative view of this is to consider that automata that use different state names are defined up to a renaming of states. What one is interested in is the equivalence class up to a renaming equivalence relation, since renaming does not change the behavior of the automaton.

Understanding the use of names is not as obvious as it may seem, and it can raise sometimes thornier technical issues, though not really here.

See for example:

• Why is it important for functions to be anonymous in lambda calculus?

• Are turing machine really countable?

• Why are pushdown automata countable?

Answer 3

The following is an attempt at explaining informally the idea of the construction. There are other ways to look at it, somewhat more theoretical. I do not know how Sipser precisely does it.

The principle of the construction of the DFA $D$ from the NFA $N_4$ is that, for a given input, the DFA $D$ simulates all the computations that $N_4$ could follow depending on non-deterministic choices it permits. In other words, for an input string $w$, $D$ will reach a state, which is precisely the set of all states that $N_4$ could reach for some computation with that same input $w$. That is why a state of $D$ is a set of states of $N_4$.

For the start state, the situation is the same. For a DFA, the start state is the state you are in when you have not read any input, or to say it differently, the state you are in after reading the input $\epsilon$. For a NFA, it is possible to reach other states from the start state without reading anything, if it has an $\epsilon$-transition to them.

In the case of $N_4$, you have $1$ as start state. But without reading anything, you have a transition to state $3$. Hence states $1$ and $3$ can both be reached by reading $\epsilon$, i.e. nothing at all. This is why the set $\{1,3\}$ is the start state of $D$. It means that $N_4$ can be (non-deterministically) in state $1$ or in state $3$ before reading any input, and in no other state.

This must remain true for all other states of $D$ (which are sets of states of $N_4$). The DFA $D$ reaches state $S$ after reading string $w$ if and only if, for each $N_4$ state $q$ in $S$, there is at least one computation of $N_4$ that reaches state $q$ when reading $w$. That is what the construction does.

Then, if a state $S$ of $D$ contains a state $q$ of $N_4$ which is an accept state, it means that for any input string $w$ that brings $D$ in state $S$, there is at least one computation of $N_4$ on input $w$ that brings $N_4$ into state $q$, and hence accepts the string $w$.

Since $D$ is supposed to accepts all the strings accepted by $N_4$, it follows that $S$ must be an accept state of $D$. There is no other way to accept the string $w$ since $D$ is deterministic by construction.

Hence, any state $S$ of $D$ that contains an accept state of $N_4$ has to be an accept state for $D$. Since $1$ is the only accept state for $N_4$, the set $\{1,2\}$ has to be an accept state of $D$.

First question

First I must say I cannot understand what you are saying in the paragraph that starts with:

My assumption---> As {2} is not in the list of accepted states ...

To begin with, as I said in a comment, you do not have lists of states, only sets of states. Second, you should talk of accept states, or accepting states, but not of accepted states.

Also, there are no new states, but only states of $N_4$, and states of $D$ which are sets of states of $N_4$. Accept states of $D$ are precisely those that contain an accept state of $N_4$, for the reasons explained above.

I cannot say much more because I do not understand what you are trying to say, what is in your mind. Why would you consider that $\{1,2\}$ cannot be an accept state of $D$, but that $\{1,2,3\}$ can be an accept state of $D$?

My further attempt to explain

The fact that both $1$ and $2$ are in this set $\{1,2\}$ indicates that there is a string $w$ for which the NFA $N_4$ can reach either $1$ or $2$ depending on non-deterministic choices in the computation. Of course, the computation that reaches state $2$ does not accept $w$. But the definition of acceptance for a non-deterministic machine is that it is enough if one computation accepts $w$, even if all other non-deterministically possible computations on $w$ fail to be accepted. In this case, it is enough that some computation on input $w$ can reach $1$.

Second question

The sentence you do not understand is apparently a problem with English. It should be read as

The start state is E({1}) which is the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself`.

I think this kind of sentence structure (with a comma instead of "which is") is called an apposition.