1
$\begingroup$

This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction (converting an NFA to a DFA).

The NFA which is being converted is as follows:

enter image description here

The argument for this then goes as follows:

Consider the NFA N of Fig. 2.15. $L(N)$ is the set of all strings of $0's$ and $1's$ such that the nth symbol from the end is $1$.

Intuitively, a DFA D that accepts this language must remember the last $n$ symbols it has read. Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, if D has fewer than $2^n$ states, then there would be some state $q$ such that D can be in state $q$ after reading two different sequences of $n$ bits, say $a_1a_2…a_n$ and $b_1b_2…b_n$.

Since the sequences are different, they must differ in some position, say $a_i \neq b_i$. Suppose (by symmetry) that $a_i = 1$ and $b_i = > 0$. If $i = 1$, then q must be both an accepting state and a nonaccepting state, since $a_1a_2…a_n$ is accepted (the $n^{th}$ symbol from the end is 1) and $b_1b_2…b_n$ is not.

If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

What's confusing me are these two lines,

Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...

and

If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

I understand the case where $i = 1$, but I don't understand how the $i \gt 1$ works, and what they mean by any of the $2^n$ subsets being $1$. How can the subsets be $1$?

$\endgroup$
1
$\begingroup$

You can ignore the first line you don't understand, that's just to give you some intuition.

For the case that $i > 1$, by assumption, after reading strings $a = a_1\cdots a_n$ and $b = b_1 \cdots b_n$, our DFA is in the same state. This means that for any string $q$, our automaton ends up in the same state after reading $aq$ as it does after reading $bq$. In particular, let $q$ be string consisting of exactly $i-1$ zeroes. Then, the automaton is in the same state for both $aq$ and $bq$, so it either accepts both or rejects both -- but that means that they have the same symbol as the $n$-th symbol from the end, which is not true: $n$-th symbol from the end in $aq$ is $a_i$, while $n$-th symbol from the end of $bq$ is $b_i$, and they are different.

$\endgroup$
1
  • $\begingroup$ Perfect, thanks! That makes it so clear! $\endgroup$ Mar 17 '18 at 3:08

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.