CSC 341 (Fall 2021)

Lab: Applying Myhill Nerode

Problem 1: Equivalence Classes

Intuitively, we can think of the equivalence classes induced by \(\equiv_L\) to be sets of string prefixes that all share the same acceptance or rejection behavior. As the Myhill-Nerode theorem tells us, each equivalence class is, itself, equivalent to a state of a DFA that recognizes language \(L\)! To gain intuition about these equivalence classes, we’ll first do some translation between DFA states and equivalence classes.

For each of the following regular languages:

  1. First, give a DFA that recognizes the language.
  2. Then from the states of the DFA, give the corresponding equivalence classes induced by the \(\equiv_L\) relation. Describe these equivalence classes as a collection of sets of strings where each set corresponds to a class. Ensure that your equivalence classes (a) are disjoint, i.e., share no strings and (b) cover all possible strings drawn from \(\Sigma^*\) although you do not need to formally prove these facts in this problem.

In all cases, the alphabet is over \(\Sigma = \{\, 0, 1 \,\}\).

We’re accustomed to developing DFAs, so going from DFAs to these equivalence classes is a useful exercise to understand the concept. However, to apply Myhill-Nerode for the purposes of proving irregularity of a language, we will necessarily need to develop the equivalence classes without the aide of a finite automata!

For these two regular languages, proceed in the opposite order:

  1. First, give the corresponding equivalence classes induced by the \(\equiv_L\) relation. Again, describe these classes as collections of sets of strings.
  2. From your equivalence classes, give a DFA that recognizes the language.

Problem 2: Nope, Not Regular, Again

Consider the language \(A = \{\, www \mid w \in \Sigma^* \,\}\) with \(\Sigma = \{\, 0, 1 \,\}\). Prove that \(A\) is irregular using the Myhill-Nerode theorem.