Regular Expression Equivalence: Which Pairs Generate the Same Language?

When two regular expressions $r_1$ and $r_2$ are equivalent, they generate the same language: $\mathcal{L}(r_1)=\mathcal{L}(r_2)$.
We will decide equivalence for each pair by reasoning from the formal meaning of Kleene star: $A^*$ is the set of all concatenations of zero or more strings from $A$, hence it always includes $\varepsilon$.

We consider the choices:

(i) $x^*$ and $x^*x$
(ii) $1(01)^*$ and $(10)^*1$
(iii) $x(xx)^*$ and $(xx)^*x$
(iv) All of the above

Key definitions and tools

• keyword Two regular expressions are equivalent if they generate the same language.
• keyword $\mathcal{L}(r)$ is the set of all strings matched/generated by regular expression $r$.
• keyword For language $L$, $L^*$ is all concatenations of zero or more strings from $L$.

We’ll repeatedly use the star expansion property:

• $\varepsilon \in A^*$
• any nonempty string in $A^*$ is a concatenation of one or more elements of $A$.

Pair (i): $x^*$ and $x^*x$

What language does each side describe?

• $x^*$ is $\{\varepsilon, x, xx, xxx, \dots\}$, because star allows zero repetitions.
• $x^*x$ means: take any string from $x^*$, then append an extra $x$.
  So $x^*x = \{x, xx, xxx, \dots\}$ and does not include $\varepsilon$.

Immediate counterexample

• $\varepsilon \in x^*$ but $\varepsilon \notin x^*x$ (because $x^*x$ always has the final appended $x$).

Therefore, $x^*$ and $x^*x$ are not equivalent.

Conclusion for (i): NOT equivalent.

(Claim justified because $*$ includes $\varepsilon$.)

Pair (ii): $1(01)^*$ and $(10)^*1$

Let $L_1 = \mathcal{L}(1(01)^*)$ and $L_2 = \mathcal{L}((10)^*1)$.

Analyze $1(01)^*`

A string in $1(01)^*$ looks like:

• start with 1
• followed by $k$ repetitions of the block 01, for $k\ge 0$ (since star allows $k=0$). So for $k=0$: string is 1
  for $k=1$: 101
  for $k=2$: 10101
  So generally: $1(01)^* = \{\, 1(01)^k \mid k\ge 0 \,\}.$

Analyze $(10)^*1`

A string in $(10)^*1$ looks like:

• take $k$ repetitions of 10, for $k\ge 0`
• then end with 1. So for $k=0$: string is 1
  for $k=1$: 101
  for $k=2$: 10101
  So generally: $(10)^*1 = \{\, (10)^k1 \mid k\ge 0 \,\}.$

Structural alignment

Notice that: $(10)^k1 = 1(01)^k \quad \text{for all } k\ge 0.$ (You can verify by expanding both sides for $k=0,1,2$; they match exactly.)

Thus $L_1=L_2$ and the two regular expressions are equivalent.

Conclusion for (ii): Equivalent.

Pair (iii): $x(xx)^*$ and $(xx)^*x$

Let $L_3 = \mathcal{L}(x(xx)^*)$ and $L_4=\mathcal{L}((xx)^*x)$.

Expand $x(xx)^*$

Strings look like:

• start with a single $x$
• then append $k$ repetitions of xx (for $k\ge 0` due to star). So for$k=0$: `x` for$k=1: xxx for $k=2: xxxxx
  So: $x(xx)^* = \{\, x(xx)^k \mid k\ge 0\,\}.$

Expand $(xx)^*x$

Strings look like:

• append $k$ repetitions of xx
• then finish with an $x$.
  So: $(xx)^*x = \{\, (xx)^k x \mid k\ge 0\,\}.$

Same lengths, same form

But concatenation is associative, so: $x(xx)^k = x\underbrace{(xx)(xx)\cdots(xx)}_{k\text{ times}} = \underbrace{(xx)(xx)\cdots(xx)}_{k\text{ times}}x = (xx)^k x.$ Therefore every string in one set equals a string in the other set (same $k$).

Conclusion for (iii): Equivalent.

(Uses the definition of Kleene star allowing $k=0$ and repetition structure.)

Final decision: Which option is correct?

• (i) is not equivalent.
• (ii) is equivalent.
• (iii) is equivalent.

So not all of the above are equivalent; therefore (iv) is false.

Answer: Only (ii) and (iii) are equivalent.