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

CSC 456/656 Study Problems

Revised September 28, 2005

The problem given here are not "challenge problems," but are exercises that you should be able to do if you understand the material of the course. They are not to be handed in.
The textbook referred to in the problems is Introduction to the Theory of Computation, by Michael Sipser. PWS. ISBN 0-534-95097-3.
I suggest trying to work each problem without looking at the hints, unless you get stuck. (But don't give up too soon.)
  1. Exercise 2.1 on page 128 of your textbook.
    In addition, give the parse tree for the string axa+ax(a+a+a)
  2. Exercise 2.44 on page 132 of your textbook Hint.
  3. Consider the following context-free grammar G, which generates a language over the alphabet {a,e,i}:
    1. S -> a
    2. S -> iS
    3. S -> iSeS
    • Prove that G is ambiguous.
    • Find an unambiguous grammar equivalent to G. Hint.
  4. Define a "binary numeral" to be any string over the alphabet {0,1} which begins with 1. (I.e., leading zeros are not permitted.) Define a "list of binary numerals" to be a string over the alphabet {0,1,#} consisting of one or more binary numerals separated by octotrophs. A list "has no duplicates" if no binary numeral is repeated in the list.
    Let L be the language of all lists of binary numerals with no duplicates. Examples. Use the pumping lemma for context-free languages to prove that L is not context-free. Hint.