Week Eleven

Monday.
--------- Nov. 17, 2008
We returned back to the DFSA that accepts strings that are multiples of 3 (when evaluated in base 2) which we designed last week. Because we are dealing with strings, we used structural induction. The proof was easy though lengthy because there were so many cases to consider.
We also talked about using \epsilon transitions to concatenate or add two machines and concluded the lecture with the definition of Nondeterministic Finite State Automate (NFSA).


Wednesday.
--------- Nov. 19, 2008
We finished off on Monday with the definition of NFSA. The main difference between DFSA and NFSA is that in the former, the current input symbol uniquely determines the next state of the automaton, while in the latter, a symbol (or even \epsilon) moves the machine to one of several possible states. Hence, a string x inputted to an NFSA might result in several paths. Determining if the NFSA accepts x or depends on finding at least one path that goes from the initial state to an acceptance state.
The bottom point in this lecture is that every NFSA has an equivalent DFSA! This can be done just by replacing each state in the DFSA states with sets of states (easier said than done).
We concluded the lecture by discussing Cartesian product of languages and FSAs. I modestly think that this tool will be a very useful in and beyond this course. I am happy because we will practice it in assignment 3.


Friday.
--------- Nov. 21, 2008
So far, we have shown that every regular expression has an equivalent NFSA and every NFSA has an equivalent DFSA. We will finish this circle by showing that every DFSA has an equivalent regular expression. So we start with a machine, add a new start and a new acceptance states, and add an \epsilon transition between the original and new start state, and between the original and new acceptance state. Finally, start removing states to get a machine that is one-state smaller every time. You will end up with a very long expressions going from the start to the acceptance state.
We used this method with a DFSA that accepts strings with odd lengths and even number of 0s. I think that the resulting regular expression was cool but long; (00+01(11)*10)*(1+01(11)*0)[0(11)*0(1+0(11)*10)(00+01(11)*10)(1+01(11)*0)]*