CS 476
Homework 1


Assigned: February 20, 2001
Due: February 27, 2001

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