1
$\begingroup$

I was given the following regular language:

For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character from the end is 1.

I know it's regular because it can be expressed as a regular expression ($\Sigma^{*}1\Sigma^{n-1}$), and I constructed a DFA and an NFA for it. I need to calculate its equivalence classes. I thought that the equivalence classes will be words that have 1 in the same place later in the word - for example one of the classes will be $L(\Sigma^{*}1\Sigma^{n-2})$, because no matter what digit will be added to all these words, the new words will belong to the original language. But I'm not sure I'm on the right track. I would love it if I could understand the process of thinking on this kind of question.

$\endgroup$
2
$\begingroup$

Whether a word and its extensions belongs to $L_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different length-$n$ suffixes, then they definitely belong to different equivalence classes.

In contrast, we can check that any two words with the same length-$n$ suffix are equivalent. Indeed, suppose $x,y$ are such words, and consider a word $z$. If $|z| \leq n-1$ then $xz \in L_n$ if the $n-i$'th letter from the end of $x$ is $1$. Since $x,y$ have the same length $n$ suffixes, the condition for $yz \in L_n$ is identical. If $|z| \geq n$, then whether $xz \in L_n$ or not only depends on $z$, and in particular holds just as well for $yz \in L_n$.

Finally, what about words which are shorter than $n$ letters? Recall the test we had above: $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. If $|w| < i$ then $w1^{n-i} \notin L_n$, and so $w$ behaves as if the $i$th letter from the end is $0$. Pursuing this route, we find that the equivalence class of $w$ depends on the length-$n$ suffix of $0^nw$, and this definition works whether $|w| \geq n$ or not.

$\endgroup$
  • 1
    $\begingroup$ Thank you. It took me a while to understand, but once I gave myself a few examples it became totally clear. One question though - if the way i understand your explanation is correct, then in the third paragraph, when you mentioned the test above - you wrote w1^(n-1), and you meant w1^(n-i). You wrote it twice. I'm not sure its a mistake so I don't want to edit that myself. $\endgroup$ – marianov Nov 23 '19 at 11:29
  • 1
    $\begingroup$ Right, thanks for the correction. $\endgroup$ – Yuval Filmus Nov 23 '19 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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