3
$\begingroup$

I am preparing for my exam in formal languages and I need some help with one question from one old exam.

enter image description here

enter image description here

I know that the number of equivalence classes of some regular language L, is the number of states of the minimal DFA for that language.

But how do I give a DFA for one of the equivalence classes ?

Thanks in advance

$\endgroup$
3
$\begingroup$

An elaborate hint: recall that the proof of the Myhill-Nerode theorem works (in one direction) by constructing a DFA for a language, given its equivalence classes.

In the constructed DFA (i.e the minimal DFA), each state corresponds to an equivalence class. We then set the accepting states to be those that correspond to equivalence classes that are contained in the language.

Now, suppose you create the DFA for the equivalence classes of $L$, without knowing in advance which equivalence classes are in L, and which aren't. If you choose one particular class, and set the state that corresponds to it to be accepting, then the language of the DFA is exactly that equivalence class, which is what you wanted.

Indeed, the property of the minimal DFA is that for every two words $w,w'$, the runs of the DFA on $w$ and on $w'$ end in the same state iff $w\equiv_L w'$.

Observe that you may end up with a DFA that is not minimal for the equivalence class.

$\endgroup$
  • $\begingroup$ Hi ! Correct me if my reasoning is not right: Say that I have a non-minimal DFA M. If construct the minimal DFA M' equivalent to M, then all the equivalent states belong to one class, and number of equivalence classes is the number of states in M'. If I choose one of the equivalence classes and give a DFA for the class, then the DFA is a "subDFA" of M, with states from the class. Is this right ? $\endgroup$ – mrjasmin Aug 29 '13 at 20:17
  • 2
    $\begingroup$ @mrjasmin Think about which words the DFA for the equivalence class L should accept. In which state would M' be, using that word? Clearly M' must have a run on that word since it is a DFA over the same alphabet as the DFA for L. $\endgroup$ – G. Bach Aug 29 '13 at 22:17
  • $\begingroup$ Can you explain further ? I know how to giva a DFA because it's just the states in the particular equivalence class, but what will be the accept states ? $\endgroup$ – mrjasmin Aug 29 '13 at 22:42
  • $\begingroup$ Edited the answer with some more explanations $\endgroup$ – Shaull Aug 30 '13 at 4:48
3
$\begingroup$

The first thing you have to do is to minimize the given DFA -- or verify that it is already minimal, it happens sometimes. I am sure you have seen this algorithm in your course. This first step will give you the minimal automaton of L, which as Shaull reminded you, can be formally defined as follows. Denote by $[u]$ the $\equiv_L$-class of a word $u$. Then the minimal automaton of $L$ is $\mathcal{A}_L = (Q, \Sigma, \cdot, [\varepsilon], F)$ where $Q = \{\ [u] \mid u \in \Sigma^*\ \}$, $F = \{\ [u] \mid u \in L\ \}$ and for each letter $a \in \Sigma$, $[u] \cdot a = [ua]$.

Now a hint for your question. What is the language accepted by $\mathcal{A}_u = (Q, \Sigma, \cdot, [\varepsilon], \{[u]\})$, obtained from $\mathcal{A}_L$ by taking only $[u]$ as final state?

$\endgroup$
  • $\begingroup$ All strings leading to [u], starting from the null string ? $\endgroup$ – mrjasmin Aug 30 '13 at 0:08
  • $\begingroup$ [B] =( 0^+) + 11 ? $\endgroup$ – mrjasmin Aug 30 '13 at 0:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.