Homework 6

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 \cup 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 n \geq 4.
a. 1 precedes 2.
b. 1 immediately precedes 2.
c. n precedes 1 and n-1 precedes 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: