DFSA

As we begin to move towards the end of the course, we've largely just finished wrapping up the lectures on deterministic finite state automaton. With the last question one the assignment having us make use of the Cartesian product, some of the important advantage and disadvantage of using DFSA to recognize strings as part of a valid set of languages have become clearer. Particularly, the process is extremely, and quite possibly only, effective when the DFSA is dealing with simple languages. The disadvantage becomes clear when we consider the number of transitions states required as the alphabet increases in size and how the problem space of the method falls prey to combinatorial explosion with small increases in the alphabet size. Infact, it seems as though the complexity of the set of strings accepted languages, perhaps measured by the number of operations involved in the equivalent regular expression, causes the problem space of the DFSA to approach combinatorial explosion as well. Thus, I suspect that the limitation on the complexity of both the language and the alphabet that a DFSA can represent is severely limited or else it requires that the statement be broken up into many smaller machines, the intersection of which is the original regular expression, a process that seems infinitely more tedious then should be necessary. Ultimately I'm curious how DFSA are used in modern computing and how we ensure the stability of their use.