Math 6

Discrete Mathematics

Readings Check section 6.3

Read Section 6.3, pages 326 ( 331. [You can skip example 6.26.]

Type in the answers below each question and email the completed document to me, or print out the document and fill it out by hand and email a scan or photo of it to me.

1) What is the purpose of the machine in example 6.20?

2) For an input string of 11100, what is the output string in example 6.20?

3) What is the relationship between the machines of figure 6.9 and figure 6.10?

4) For an input string of 111000111, what is the output string in example 6.21?

5) Is it possible to construct a finite state machine that recognizes strings in the language

A = {01, 0011, 000111,…} ? [See example 6.23]

6) Considering the machine of figure 6.9 and the one in figure 6.12(a), in general how many states are needed to construct a FSM that recognizes a sequence of length k ?

7) For the finite state machine in figure 6.12(b), what is the output string if the input string is composed of one million zeros followed by 0101 ? Be precise in your answer.

8) Is the finite state machine in figure 6.12(b) strongly connected ? Explain why / why not.

After submitting this form, go on to watch the videos, read the notes, and start the homework assignment for section 6.3. Ask any questions that arise at any point in the process. When the homework assignment is done, and you feel that you have a solid understanding of the homework and the section, then take the quiz for section 6.3.