Does εε = ε in formal languages?

98 Views Asked by At

For example would ∅*(ε) = εε = ε? Noting that ∅* = {ε}.

Takes this language equation:

X1 = ∅ + bX1 + aX2
X2 = ε + ∅X1 + ∅X2

Apply arden's lemma to X2.

X2 = ∅*(ε + ∅X1)
   = ∅*ε + ∅∅X1
   = εε + ∅∅X1

Does that seem right for X2 in this case?

I know it doesn't make sense to apply arden's lemma to the 2nd equation in this case but I'm trying to implement an algorithm that turns an equation system into a regex through brzozowski algebraic method.

1

There are 1 best solutions below

4
On BEST ANSWER

The empty word $\epsilon$ is the neutral element for concatenation in formal languages so for any word $a$, $\epsilon a = a\epsilon = a$. Taking $a=\epsilon$, you indeed get $\epsilon \epsilon = \epsilon$.