University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page

CS 456/656 Assignment 4
Due date: November 28, 2006, 4:00.
-
Use the pumping lemma for regular languages to
prove that {anbn+2} is not regular.
-
Use the pumping lemma for context-free languages to
prove that {anbn+2an} is not context-free.
-
Draw the state diagram of a Turing Machine that accepts the language over
{0,1} of all strings which have the same number of zeros as ones.
-
Categorize each of the following languages as either recursive,
recursively enumerable but not recursive, or not recursively enumerable.
-
The halting problem.
-
The intersection of any two regular languages.
-
The diagonal language.
-
The Post correspondence problem.
-
The programming language Pascal.
-
The language of all strings of the form < n > d where < n >
is the decimal
numeral for a positive integer n, and where d is the nth
digit of the decimal expansion of pi (the well-known ratio of the
circumference of a circle to its diameter).
-
The language of all fractions, written the way you learned in kindergarten,
such as "17/31".
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
Back to
Course Page