MTH210

Tutorial 8

 Ryerson University

Finite State Automata

Readings

This tutorial covers material from sections 12.1 and 12.2 of the textbook. Page and exercise numbers are from the course textbook.

The first few questions in each tutorial set are generally easier. Make sure that you do some of the more challenging problems as these will be closer to the level of the quiz questions.

Your TA will take up some of these questions in class. However, there will not usually be time to cover all the assigned questions. You may ask your TA about any of the assigned problems if you have questions.

You may also be asked to work on problems during the tutorial. Only students who work diligently on the assigned material will receive the attendance mark.

Tutorial 8

  1. p. 745 #21, 27

  2. p. 745 #32, 35, 38

  3. p. 762 #6, 16

  4. p. 762 #9, 19

  5. p. 762 #22, 27

  6. Use the method of forming the ``complement'' of a FSA to construct a FSA with at most 4 states to recognize the language over {a,b,c} of all strings which do not contain bab as a substring.

This page is maintained by Peter Danziger.
Last modified Thursday, 04-Mar-2010 15:43:52 EST