Computer Science 656: Automata and Formal Languages
Spring 2001
Graduate Homework Assignment 1.
Due Monday, February 12, 2001
You may discuss this assignment with other students in the class, or other
persons. But you must actually write the assignment in your own hand.
You must turn in the homework on letter-sized paper, with your name at the
top of each page. Use pen or pencil, any color.
Do not type your homework, and do
not write your homework as a computer file and turn
in a printout.
I will personally grade this assignment.
-
Let E be the set of regular expressions over the binary alphabet.
Prove that E is not a regular language.
It might be necessary to use material from the book which is not
covered in class. You can even use material from other books, but
in fact, our textbook contains enough to work this problem.
-
Find an NFA with 3 states which is not equivalent to any DFA with 3
or fewer states, and prove your answer, using minimization.
-
Prove that a set of natural numbers is regular if and only if it is the union
of finitely many arithmetic series. An arithmetic series can be either
finite or infinite. For example, {5}, {2,7,12,17,22,...}
and {4,8,12,16,20,...} are arithmetic series, thus their union
{2,4,5,7,8,12,16,17,10,22,...} is a regular set of natural numbers.
This is really two proofs: to prove that every union of finitely many
arithmetic series is regular,
and to prove that every regular set of numbers is the union
of finitely many arithmetic series. If you can only do one, then just turn
it in without the other half.

Back to
Course Page