Final exam is coming!

This is the last week of class. Then we are going to review at home and be ready for the final exam!

CSC236 exam is on Dec.12nd.

To do list before final:

   1. Review every lecture notes.
   2. Do all the tutorial questions again.
   3. Review each quiz and assignment.
   4. Do the past exams.
   5. Read textbook if there are questions.
   6. Go to office hour if needed.

BE READY AND CHEER UP!

Tutorial 8

One question on the tutorial I found very interesting -- the second question on tutorial 8.

It asked to devise a DFSA that accepts the language of strings over {0,1}, with an odd number of 1s and and even number of 0s. From the DFSA, devise the regular expression that denotes the same language.

So first of all, devise a DFSA that has four states. i.e. keep every states and find the relationship between.

Then remove one state at a time and modify all the states that have a relationship with this removed state.

Remove states until there are only two states left: the beginning state and the accepting state.

Finally, use a singe letter to represent a  string and write out the regular expression.

This is how I did this problem.

A binary can have an even number of 1s and even number of 0s (EE), or an even number of 1s and an odd number of 0s (EO), or an odd number of 1s and an even number of 0s (OE), or an odd number of 1s and an odd number of 0s (OO). So there are four states : q1, q2, q3,q4 repectively.

The beginning state should an empty string. In this case, there should be no 0s or 1s in this string, so the number of 1s and 0s are both even (there is zero 0 and zero 1). This is in the first state.

The accepting state should by a string that has an odd number of 1s and an even number of 0s. i.e. the third state.

There are two choices to add to the first state: 1 or 0.

If add a 0 to the beginning state, there will be one 0 and zero 1, so there will be an even number of 1s and an odd number of 0s. This is in the second state.

If add a 1 to the beginning state, there will be one 1s and zero 0s, so there will be an odd number of 1s and an even number of 0s. This is in the third state.

Similarly, there are two choices to add to the second state.

The second state has an even number of 1 and an odd number of 0, so if add a 0 to the second state, there will be an even number of 1s and an even number of 0s. This goes back to the first state.

If add a 1 to the second state, there will be an odd number of 1s and an odd number of 0s. This is in the fourth state.

Then let's talk about the third state.

The third state has an odd number of 1s and an even number of 0s. If add a 0 to the third state, there will be an odd number of 1s and an odd number of 0s. This goes to the fourth state.

If add a 1 to the third state, there will be an even number of 1s and even number of 0s. This will go back to the first state.

Same to the fourth state.

The fourth state has an odd number of 1s and an odd number of 0s. If add a 0 to the fourth state, there will be an odd number of 1s and even number of 0s. This goes to the third state.

If add a 1 to the fourth state, there will be an even number of 1s and an odd number of 0s. This goes to the second state.

Once the string goes back to the first state, whatever the next string is 1 or 0, it always going to loop in between these four states.

The graph is as below:

 

First remove the fourth state of the device. i.e. remove OO state.

 

So we can get from EO to OE by adding a 10 and get from OE to EO by adding a 01.

 

Adding 11 to EO, we are still in state EO and adding 00, we are still in state OE.

 

 

 

Similarly, we can remove one more state, EO.

 

 

 

Then we represent each string by a unique letter: R represents 0(11)*0, P represents 1 + 0(11)*10, Q represents 00  + 01(11)*10 and T represents 1 + 01(11)*10.

 

There are two ways to get from state EE to state OE : go from EE to OE or first go from EE to OE, then from OE to EE and then back to OE. So the regular expression for this device is

R*P(Q + TR*P)*.