Myhill-nerode theorem, Theory of Computation

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes the same language will have the same number of states and the same edges, differing in no more than the particular names it gives the states. If we apply this to A and L(A) is empty then we will obtain a DFA that is isomorphic to any minimal DFA that recognizes ∅. In particular it will contain just a single state and that state will not be an accepting state. (Being a DFA, that state will have a self-edge for every symbol in the alphabet.) It's pretty easy to check if this is the case for the minimized version of A. We return "True" iff it is.

Posted Date: 3/21/2013 1:52:04 AM | Location : United States







Related Discussions:- Myhill-nerode theorem, Assignment Help, Ask Question on Myhill-nerode theorem, Get Answer, Expert's Help, Myhill-nerode theorem Discussions

Write discussion on Myhill-nerode theorem
Your posts are moderated
Related Questions
Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give


The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will w

How useful is production function in production planning?

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie



We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while