3.1k views
0 votes
Prove that for any language L over an alphabet Σ,L∗=L + if ϵ ∈L

User Tinwor
by
7.9k points

1 Answer

0 votes

Final answer:

To demonstrate that L* equals L+ given that the empty string ε is in L, we leverage the definitions of Kleene star and positive closure and the properties of string concatenation.

If ε is part of L, every string in L+ is also in L* and vice versa, showing that L* and L+ are equivalent under this condition.

Step-by-step explanation:

To prove that for any language L over an alphabet Σ, L* is equal to L+ if the empty string ε is in L, we should first understand the meaning of the notations L* and L+.

The notation L* refers to the Kleene star of L, which is the set of all strings that can be made by concatenating zero or more strings from L together. This means it includes the empty string ε because concatenating zero strings from L would result in ε.

On the other hand, the notation L+ refers to the positive closure of L, which is the set of all strings that can be made by concatenating one or more strings from L.

Now, let's consider the condition ε ∈ L. If ε is in L, any string in L+ can also be seen in L* because you can prepend the empty string (ε) to any string in L+ without changing its value, effectively demonstrating L+ ⊆ L*.

Conversely, since we are allowed to concatenate zero strings from L to make ε in L*, and L contains ε as well as other strings, we can concatenate any number of these strings to reproduce any element in L+.

Therefore, L* ⊆ L+ under the condition that ε ∈ L. Given that we have both L+ ⊆ L* and L* ⊆ L+, we can conclude that L* = L+ when ε ∈ L.

User Tomas Kulich
by
8.6k points