Regular Expression definitions, as a rule, what is always true?

Question

If I have two regular expressions $\sf S$ and $\sf T$, what is always true of these?

options:

1. Both $\sf(SS \mid T)^\ast$ and $\sf(TSS)^\ast$ are subsets of $\sf(TSS\mid STS\mid SST)^\ast$
2. $\sf(TSS)^\ast$ is a subset of $\sf(SS\mid T)^\ast$
3. Neither $\sf(SS\mid T)^\ast$ nor $\sf(TSS)^*$ is a subset of the other.
4. $\sf(SS\mid T)^\ast$ is a subset of $\sf(TSS)^{\ast\ast}$

Here is my issue: I do not think any of these are always true (which is obviously not the case).   (At first I thought 1 but after re-reading my notes, I'm unsure) Can anyone point or hint me in the correct direction WITHOUT telling me which number is correct?

Answer 1

Some notes (most redundant because alternation was meant instead of Kleene plus repetition):

• $\sf (S\mid T)$ matches either $\sf S$ or $\sf T$. So $(S\mid T)^\ast$ matches all strings of zero or more length where each character is either $S$ or $T$; which also may be expressed as $(S^\ast T^\ast)^\ast$

---

• $\sf SS^+$ means two or more repeats of $\sf S$

• $\sf SS^+S, SSS^+, S^+SS$ all mean three or more repeats of $\sf S$ .   They are the same pattern.

* An expression is a subset of another if all of the strings matched by the former are (some of the) strings matched by the later.   This means that, at the very least, you can eliminate expressions that don't start or end in the same symbol.

• That is: $(XY)^\ast \not\subseteq (XYX)^\ast$ because almost all of the former will terminate with a $Y$ (the exception is the empty string), while almost all of the later will terminate with an $X$ (same exception).
• Since the OP meant alternation, this is now not so helpful.