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

CSC 456/656 Assignment 7

Due date: Tuesday, April 1, 2014, 4:00 PM.

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.
  1. Let A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}, and D={0,1,2,3,4,5,6,7,8,9}.
    In some computer languages, every identifier is required to be a string over A+D whose first symbol is in A, and an unsigned number is a non-empty string over D. Then A(A+D)* and DD* are the languages of identifiers and unsigned numbers, respectively.
    1. Give a context-free grammar for the language of all identifiers.
      Hint: use the regular expression as a guide.
    2. If L is a language whose members are string which have some kind of meaning (for example, algebraic expressions, or programs) a parse tree for a string respects the semantics if it is naturally consistent with meanings of strings.
      That means, specifically, that each node in the parse tree has value (not necessarily a numerical value) such that the value of an internal node can be determined by looking at the values of its children. For example, in a parse tree for the algebraic expression x-y+z, there should be an internal node whose leaves constitute th substing x-y, but there cannot be an internal node whose leaves constitute the substring y+z.

      Give an unambiguous context-free grammar for the language of all unsigned numbers, as defined above, which is consistent with the semantics.
      Hint: If you use the regular expression DD* as a guide, you will probably get the wrong grammar, i.e., a grammar which generates the language, but does not respect the semantics.
    Note that the issue of semantics does not arise for the language of identifiers.

  2. A 2-PDA is the same as a PDA, except that it has two stacks instead of one.
    Show that every Turing machine can be emulated by a deterministic 2-PDA.
    In a problem like this, students always wonder how much detail they are supposed to give. A really complete answer is a computer program, which takes as input an encoding of a Turing machine, and outputs the encoding of an equivalent determinist 2-PDA. Of course, that would be accompanied by a proof that the resulting 2-PDA is actually equivalent to the input TM. No one, least of all me, would want to grade that!
    In class, I have shown how various machines can be emulated by Turing machines. Each of those constructions I have given is informal, but (I hope) convincing. The same rule applies to this homework. What you write should convince the grader that you could, given sufficient time, write the program described above. There shouldn't be any code in your answer. Diagrams and examples will certainly help.

Back to Course Page