Math 6

Weekly Summary, Week 5, Chapter 6, Discrete Mathematics Name:

Due on Sunday, September 30, by midnight.

Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.

1) In example 6.24, figure 6.13, we are presented with a 1(unit delay machine. It has 3 states. In example 6.25, figure 6.14(b), we have a 2(unit delay machine. It has 7 states. a) How many states will a 3(unit delay machine require? b) How many states will a 5(unit delay machine require?

2) In the following FSM there are 11 states labeled s1, s2,…, s11. There are no outputs. The letters next to the arrows are characters in the input string. The starting state is s1.

a) What are the states that are reachable from s6 in this FSM?

b) What are the sink states, if any, in this FSM?

3) The following FSM accepts strings from {0, 1}* . The three states are called 01, 00, and 11. The starting state is 01. Input and output are marked on each arrow as input/output. For what strings does the machine output a 1? In other words, what is it supposed to detect? Give your answer in the form of the languages given in 6.1 problem #12 a) to f). [Hint: some answers that are in the correct form, but are wrong, are {0}*{1}*, {1}{0}+{11}, and {1}*{0}+ {10}* . The third one is close but needs modification.]

4) Give a recursive definition for the language A over {0, 1} containing exactly all of the binary strings in which 11 is never a substring. For example, A contains the strings 0, 1, 01, 00, 000, 001, 100, 1010, and so on. Use examples 6.14 and 6.15 to guide you. Be sure to test your definition thoroughly. It must not produce strings that contain 11, such as 11, 110, 011, 1100, and so on.

5) S is the language over ( = {a, b, c, d} containing all strings that start with at least 2 c's, followed by any number of b's, followed by 3 a's, followed by an even number of b's, followed by at least one d. For example, S contains ccbbaaabbd, cccaaabbbbddd, and so on. Write S symbolically in the manner of section 6.1, problem # 12 a) ( f). Example 6.12 will also be helpful.

bonus: How many strings in {000, 1}* have length 12?