lasasbuddies.blogg.se

This is especially necessary when finite automata produceįirst, how does one find equivalent states, and then, exactly how Way to say this is that the machine does the same thing when started inĮither state. X as input, it either accepts in both cases or rejects in both cases. If and only if for every string x, if M is started in either state with

Two states in a finite automaton M are equivalent Here is one formulation of what Mooreĭefinition. To do this, we must agree upon theĭefinition of equivalent states. It seems that the key to making finite automata smaller is to recognizeĪnd merge equivalent states. Merging states like this should produce a smaller automaton that accomplishes exactly the same task as our original one.

So, why not merge them and form a smaller machine? In the same manner, we could argue for merging states s 0 and s 5. Accepting states are colored yellow while rejecting states are blue.įigure 1 - Recognizer for (aa + b)*ab(bb)*Ĭloser examination reveals that states s 2 and s 7 are really the same since they are both accepting states and both go to s 6 under the input b and both go to s 3 under an a. Consider the finite automaton shown in figure 1 which accepts the regular set denoted by the regular expression (aa + b) *ab(bb) *.