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, October 29, 2013, 1: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.
-
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.
-
Give a context-free grammar for the language of all identifiers.
Hint: use the regular expression as a guide.
-
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.
-
Work Exercise 3.1 on page 187 of the third edition.
Exercise 3.1 on page 159 of the second edition.
Exercise 3.1 on page 147 of the first edition.
-
Work Exercise 3.2 on page 187 of the third edition.
Exercise 3.2 on page 159 of the second edition.
Exercise 3.2 on page 147 of the first edition.
-
Work Exercise 3.8(b) on page 188 of the third edition.
Exercise 3.8(b) on page 160 of the second edition.
Exercise 3.8(b) on page 148 of the first edition.
-
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