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
shell script to print table in given range


De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

distinguish between histogram and historigram

design an automata for strings having exactly four 1''s

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e