The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can define

$$r_1 \cong r_2 \qquad\text{iff}\qquad \mathsf{language}(r_1) = \mathsf{language}(r_2) $$ and likewise for ${A}_1 \cong {A}_2$. My question is about a natural generalisation: fix a set $S$ and define

$$r_1 \cong_{S} r_2 \qquad \text{iff} \qquad \mathsf{language}(r_1)\cap S = \mathsf{language}(r_2) \cap S$$

I call this "equivalence-up-to $S$". Clearly $\cong$, the standard equivalence, arises as special case with $S = \Sigma^*$. Equivalence-up-to a set is a natural and versatile construction, not restricted to regular languages, and I've seen it used before.

Question: Where can I find equivalence-up-to a set in older papers? Does it have a name, can it be found in one of the well-known textbooks on automata theory?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.