Finding the equivalence classes of a singleton set

120 Views Asked by At

Given a set L which contains only the string s = 10100, I need to find the equivalence classes [t], where t is a string that is not a prefix of s. (Σ = { 0, 1 }).

I've drawn the smallest DFA recognizing L, which has 7 states, meaning there should be 7 equivalence classes for L. However, I can't seem to figure out what those seven classes should be. Here's what I've come up with thus far. (I am almost certain that this is incorrect)

t = ε10100. L/t = { ε10100 }, [ t ] = { ε10100 }

t = 1ε0100. L/t = { 1ε0100 }, [ t ] = { 1ε0100 }

t = 10ε100. L/t = { 10ε100 }, [ t ] = { 10ε100 }

t = 101ε00. L/t = { 101ε00 }, [ t ] = { 101ε00 }

t = 1010ε0. L/t = { 1010ε0 }, [ t ] = { 1010ε0 }

t = 10100ε. L/t = { 10100ε }, [ t ] = { 10100ε }

t = 10100. L/t = { 10100 }, [ t ] = { 10100 }

Thanks in advance, and I apologize if I've misunderstood anything.

1

There are 1 best solutions below

0
On BEST ANSWER

The classes must be a disjoint union of $\Sigma^*$. Your classes all seem to be singleton sets and even all identical, because the $\epsilon$ in different positions of the string are empty strings. So although I do not fully understand your solution, I am quite certain that it is incorrect.

The solution depends on the definition of syntactic congruence you use. Probably the most common one is the one with context only on the left side: $$ u\sim_L v :\leftrightarrow \forall w\in\Sigma^* (uw\in L \leftrightarrow vw\in L).$$

So, for example, take the string $t=101$. It can be extended to the right only by $00$ to obtain a string in $L$. There is no other string that results in a string in $L$ by extension by $00$. Therefore $101$ is in a equivalence class only by itself: $[101] = \{101\}$.

The same argument works for $\epsilon$, $1$, $10$, $1010$, and $10100$. Thus there are six classes that are singleton sets.

All the other strings cannot be extended to the right in any way to form a string in $L$. So they form the seventh class: $$[0] = \Sigma^* \setminus \{\epsilon, 1, 10, 101, 1010, 10100\} = [00] = [010] = \cdots$$