Computer Science 456/656 Fall 1998 Short Quiz, September 10, 1998

Name: No books, notes, or scratch paper. Use pen or pencil, any color. Use the rest of this page and the backs of the pages for scratch paper. If you need more scratch paper, it will be provided. The entire test is 50 points.

1. True or False. [5 points each] (a) The language of all binary numerals for prime numbers is regular.

(b) The language of all binary numerals for powers of 2 is regular.

(c) Every subset of a regular language is regular.

(d) A language L is regular if and only if there is some NFA M which accepts L.

2. Fill in each blank with one word. [5 points each blank]

(a) Every NFA with n states is equivalent to a unique DFA, which has at most states. (I want the formula.)

(b) If M is a machine, then, given any configuration x of M, there is at most one configuration y of M such that M can change from x to y in one step.

3. Draw a minimal DFA which accepts the language of all strings over {0, 1} which contain at least one instance of 00 as a substring. [15 points]