proving a implication with regular expressions

159 Views Asked by At

I'm trying to prove the following implication to be false:

R*(T+S) $\equiv$ R*(TS) $\implies$ T $\equiv$ S.


Proof:

We have that IF R*(T+S) $\equiv$ R*(TS) THEN T $\equiv$ S

Let R, T = ∅ and S = ε


Consider:

R*(T+S)

$\equiv$ ∅*(∅ + ε) [by definition]

$\equiv$ ε(∅ + ε) [by kleene star property]

$\equiv$ ε(∅) [annihilator for concatenation]


R*(TS)

$\equiv$ ∅*(∅ε) [by definition]

$\equiv$ ε(∅) [annihilator for concatenation]

$\equiv$ ∅ [annihilator for concatenation]


We have that LHS $\equiv$ RHS, but to get this, T = ∅ and S = ε. Therefore T $\not\equiv$ S


Apparently, this is incorrect, but I don't understand why.

1

There are 1 best solutions below

1
On

There are two problems, the second arising from the first. First, your first calculation is incorrect; it should be

$$\begin{align*} R^*(T+S)&\equiv\varnothing^*(\varnothing+\epsilon)\\ &\equiv\epsilon(\epsilon)\\ &\equiv\epsilon\;. \end{align*}$$

Hence the second (and crucial!) problem: $R^*(T+S)\equiv\epsilon\not\equiv\varnothing\equiv R^*(TS)$, so this can’t be a counterexample to the implication in question, as it doesn’t satisfy the premise of that implication.

HINT: Try $S=a+\epsilon$ and $T=\epsilon$.