Homework 1

Due: February 27, 2001

Give a generic method for constructing an NFA *M*_{n}
to accept the language *L*_{n} for a given *n*;
where *L*_{n} is the set of all strings of 0's and 1's
such that the *n*th symbol from the end is 1. What is the number
of states of *M*_{n} as a function of *n*? What is
the number of states of the DFA *M'*_{n} equivalent to
*M*_{n}?