2
$\begingroup$

I can't seem to find anything about this and I wonder if I'm asking a silly question.

If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated?

If yes, would you concatenate the first two and concatenate the result to the third one or would you concatenate it as $\{ace, ade, acf, adf, bce, \ldots\}$? And what if one of the languages only contained the empty word $ε$?

$\endgroup$
3
$\begingroup$

Concatenation is associative: $$ (L_1L_2)L_3 = L_1(L_2L_3) = \{w_1w_2w_3 : w_1 \in L_1, w_2 \in L_2, w_3 \in L_3\}. $$ We denote the common value by $L_1L_2L_3$.

A class of languages closed under concatenation of two languages is also closed under concatenation of three or more languages, as a simple induction shows.

The "zero" element for concatenation is the empty language $\emptyset$, which satisfies $L\emptyset = \emptyset L = \emptyset$. The "one" element for concatenation is the language consisting of only the empty word $\{\epsilon\}$, which satisfies $L\{\epsilon\} = \{\epsilon\}L = L$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.