rel="canonical" href="https://www.selfstudyworld.com/" /> Myhill-Nerode Theorem Skip to main content

Myhill-Nerode Theorem

Myhill-Nerode Theorem

In the theory of formal languages, the Myhill-Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, WHO established it at the University of Chicago in 1958(Nerode 1958).


Statement of the Myhill-Nerode Theorem

Given a language L and a combination of strings x and y, define a characteristic extension to be a string two such specifically one in all the 2 strings xz and yz belong to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y. It is easy to show that RL is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.

The Myhill-Nerode theorem states that L is regular if and only if RL has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in RL. In particular, this implies that there is a unique minimal DFA with a minimum number of states (Hopcroft& Ullman l979).


Myhill-Nerode Theorem Proof

if L is a regular language, then by definition, there is a DFAA that recognizes it. with only finitely many states. If there are n states, then partition the set of all finite strings into n subsets. where subset S, is the set of strings that. when given as input to automaton A, cause it to end in state i. For every two strings, x and y that belong to the same subset, and for every choice of a third-string z automaton A reaches the same state on input xz as it reaches on input yz, and therefore must either accept both of the inputs x: and yz or reject both of them. Therefore, no string Z can be a distinguishing extension for x and y, so they must be related by RL. 

Thus, S is a subset of an equivalence class of RL. Combining this fact with the fact that every member of one of these equivalence classes belongs to one of the sets Si this gives a many-to-one relation from states of A to equivalence classes, implying that the number of equivalence classes is finite and at most M.

In the other direction, suppose that RL has finitely many equivalence classes. In this case. it is possible to design a deterministic finite automaton that has one state for each equivalenée class. The start state of the automaton corresponds to the equivalence. class containing the empty string, and the transition function from a state X on input symbol y takes the automaton to a new state, the state corresponding to the equivalence class containing string by, where x is an arbitrarily chosen string in the equivalence class for X. 

The definition of the MyhillNerode relation implies that the transition function is Well defined: no matter which representative string x is chosen for state X, the same transition function value will result. A state of this automaton is accepting if the corresponding equivalence class contains a string in L; in this case, again, the definition of the relationship implies that all strings in the same equivalence class must also belong to L, for otherwise, the empty string would be a distinguishing string for some pairs of strings in the class.

Thus, the existence of a finite automaton recognizing L implies that the Myhill-Nerode relation has a finite number of equivalence classes, at most equal to the number of states of the automaton, and the existence of a finite number of equivalence classes implies the existence of an automaton with that many states.

Popular posts from this blog

Limitations of Terzaghi Theory

Limitations of Terzaghi Theory The value of the coefficient of consolidation has been assumed to be constant.  The distance d of the drainage path cannot be measured accurately in the field. The thickness of the deposit is generally variable, and an average value has to be estimated.  There is sometimes difficulty 1n locating the drainage face, sometimes thin previous seams that can act as good drainage face are missed in the boring operations. The equation is based on the assumption that the consolidation is one-dimensional. In the field, the consolidation is generally 3-dimensional. The lateral drainage may have a significant effect on the time rate of consolidation. The initial consolidation and secondary consolidation have been neglected. Sometimes these form an important part of the total consolidation. In actual practice, the pressure distribution may be far from linear or uniform. Read More Muller-Breslau principle

Price Guard Wire Method

Price Guard Wire Method Some form of  Price Guard Wire Method  is generally used to eliminate the errors caused by leakage currents over insulation. Fig. 3.14 illustrates the operation of This Method. In fig 3.14(a), a high resistance mounted on a piece of insulating material is measured by the ammeter voltmeter method. The micro-ammeter measures the sum of the current through the resistor (IR) and the current through the leakage path around the resistor. The measured value of resistance computed from the readings indicated on the voltmeter and the microammeter, will not be a true value but will be in error.   Figure 3.14 Application of  guard  circuit for measurement of high resistance In fig, 3.14 (b), the  guard  terminal has been added to the resistance terminal block. The  guard  terminal surrounds the resistance terminal entirely and is connected to the battery side of the micro-ammeter. The leakage current IL now

Streamer Theory of Breakdown in Gases

Streamer Theory of Breakdown in Gases According to the Townsend theory firstly, current growth occurs as a result of the ionization process only. But in practice, breakdown voltages were found to depend on the gas pressure and the geometry of the gap. Second chances time lags of the order of 10-5 s, but practically it was observed to occur at a very short time of 10-8 s. Also, the Townsend mechanism predicts a very diffused form of discharge, that actually discharges were found to be filamentary and irregular. Townsend's mechanism failed to explain all these observed phenomena and as a result, The Streamer theory was proposed. The theory predicts the development of a spark discharge directly from a single avalanche in which the space charge developed by the avalanche itself is said to transform the avalanche into a plasma steamer. In Fig 1.7, a single electron starting at the cathode by ionization builds up an avalanche that crosses the gap. The electrons in the a