|
This assignment is due at start of your section on February 4. Please
read the class policies for collaboration,
cheating, and late assignments. Be extremely neat and concise in
writing up your answers; answers that are not clear to the grader, are
difficult to read or understand, or are too long, will receive no
credit. In your write-up, please use the actual Greek letters and
math symbols rather than spelling them out in English as done below.
We did that only because HTML currently doesn't support math
symbols.
|
| IMPORTANT: Note that this assignment is in three parts: I, II, and III. You must hand in each part separately, so do each part on separate pieces of paper. Put your name, your section, and the part number at the top of the first page of each part. Be sure that the pages for each part are held together (stapling preferred). Basically, think of this as three short, separate problem sets. Points will be deducted if you do not follow these directions. |
2. Arithmetic with finite automata. Let SIGMA = { 0,1,2,3,4,5,6,7,8,9 }. Let L be a language over SIGMA, L = { x : the number with decimal notation x is divisible by 3, and x contains no two consecutive identical digits }. For example, 12 is in L, because 12 is divisible by 3. But 99 is not in L, because even though 99 is divisible by 3, it contains two consecutive identical digits. Show that L is regular. (Hint: a number is divisible by three if and only if the sum of its digits is divisible by three.)
a) { ambn : m does not equal n }
b) { ambn : m < n < 2m }
c) { w is a string in {a,b}* : each prefix of w has at least as
many a's as b's }
2. Ambiguity and parsing. Do L&P problem 3.2.2 . Also, choose a string in the language that has multiple derivations and draw at least two of the possible parse trees for it.
2. Flipping for a Turing machine. Diagram a Turing machine that computes f(w) = wR over SIGMA = {a,b}. (Hint: use R and L as defined in 4.1; it'll vastly reduce the amount of writing you'll have to do.)