[Math] Lambda and concatenation of languages.

formal-languages

new to math exchange but i'll give this a shot.

I'm working with formal languages here, specifically with concatenation. Concatenation is defined as:

S1 o S2 = { vw : v ∈ S1, w ∈ S2 }

Since every language includes λ(empty string) in the set, wouldn't something like the following be true?

S1 = {a}; S2 = {b}; S1 o S2 = {a, b, ab}.

After looking i've been seeing answers more along the lines of:

S1 = {a}; S2 = {b}; S1 o S2 = {ab}

I haven't been able to figure out why. My question is, is λ ignored in a concatenation operation between two languages?

Thanks,

-Steve

Best Answer

Given $S_1 = \{a\}$ and $S_2 = \{b\}$, by definition $S_1 \circ S_2 = \{ab\}$. The set $\{a\}$ does not contain the empty string. The following reasoning is false: "every language includes λ in the set".

If it were $S_1 = \{a, λ\}$ and $S_2 = \{b, λ\}$ then you would have $S_1 \circ S_2 = \{ab, a, b, λ\}$.

Edit: If you generate a language using the Kleene-star operator: Kleene Star, then you will always have the empty string, but not in general.

Related Question