Homework 6 is due on Wednesday, August 4th.
0. Read Chapter 12. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:
- Found most difficult
- Found most surprising
- Would like to have discussed in the next lecture
1. Construct deterministic finite-state automata that recognizes each of these languages.
a. The set of bit strings that have at most two 0s
b. The set of bit strings that have exactly two 0s.
2. Prove Pumping Lemma (problem 22, page 827).
3. Construct finite-state automata that recognizes the regular sets:
a. 10*1*
b. 0*(10 
11)*
11)*4. Construct a Turing machine that computes the function f(n) = 2n for all nonnegative integers n.
5. There are ten red and ten blue balls in a box. Randomly get out 5 balls. What is the probability to get 5 red balls?
6. What is the probability of these events when we randomly select a permutation of {1, 2, .., n} where 
.
.a. 1 precedes 2.
b. 1 immediately precedes 2.
c. n precedes 1 and n-1 precedes 2
Advertisements
Filed under: Uncategorized |
Leave a Reply