week.eleven

reminder: problem set #6 due friday!

on monday, we continued the dfsa topic by proving the correctness of the machine - i.e: the correctness of the state invariants. the key is to set a string x as a concatenation of the string y and a symbol a (x = ya). when we assume that y takes the machine from the starting state to some state q, what will happen if the machine transitions from state q and the machine reads in the symbol a = 0, 1 - i.e.: what state would a take the machine next? this is taken care of in the induction step of the proof. the proof seemed a bit complex for me - it takes into account understanding the machine as a whole and knowing where each state transitions into upon reading a symbol from the alphabet. because of this, it is common for me to get lost in the induction step of the proof.

on wednesday, we started on he topic of non-deterministic finite state automata (nfsa). prof heap showed that every fsa and regex are the same if the denote the same language. furthermore, for every regular expressions, there's a nfsa that denotes it. the definition of a nfsa awfully similar to dfsa - the only difference being the transition function, which takes in a state, and a symbol from the alphabet unioned with the empty string, \epsilon, and it returns a set of states. an important fact is that every regex has a nfsa and every nfsa has dfsa - thus by transitivity, every regex has a dfsa (well, almost all). what about the converse? does every dfsa has a regex that denotes it? moreover, fsa machines can denote many of the language operations - namely the complement, reversal (where the starting state becomes the accepting state, and vice versa), and union. it is, however, almost imposible to construct a machine that denotes the intersection of two languages - for this case, cartesian product is used. the difference in a cartesian product machine is, yet again, in the transition function. instead of accepting a state, it accepts an ordered pair of states, and also returns an ordered pair of states - each state in the cartesian product belongs to either machine denoted by either language. this technique sure saves a lot of time rather than constructing a machine that denotes an intersection of two languages from scratch.

in friday, as it turns every dfsa has an equivalent regex that denotes it. in order to obtain a regex from a dfsa, we need to add new states as the starting and accepting states with \epsilon-transitions going out of the starting and coming into the accepting states. and start removing the states one by one until there are only the starting and accepting states left. this may sound easy aesthetically, but the process in obtaining the particular rfinal regex can be confusing enough for anyone to get lost if you miss recovering the pathway in and out of a state, while at the same time creating a regex to represent that that particular pathway. this technique is particularly challenging, but positively challenging that helps you understand the interrlationship between dfsa and regexes. i wouldn't mind doing a question like this on the final exam.