0
$\begingroup$

Given an alphabet $\Sigma$, $P (\Sigma^*)$, the power set of $\Sigma^*$, is a monoid, with language concatenation as morphism.

  1. What is the identity: the empty language, or the language consisting of only the empty string?

  2. What is the difference between concatenating a language with the empty language and with the language consisting of only the empty string?

Thanks.

$\endgroup$
2
  • $\begingroup$ I thought that language concatenation is defined pointwise. Shouldn't $L\emptyset=\emptyset$, then? $\endgroup$ – R. Burton Jun 23 '20 at 23:52
  • $\begingroup$ What is the definition of language concatenation? $\endgroup$ – Tim Jun 24 '20 at 0:08
3
$\begingroup$

For languages $L_1$ and $L_2$, the concatenation of $L_1$ with $L_2$ is defined elmentwise as:

$$L_1L_2=\{s_1s_2\mid s_1\in L_1\land s_2\in L_2\}$$

(at least in every case that I have seen)

The concatenation of a language $L$ with the empty languae is thus:

$$L\emptyset = \{s_1s_2\mid s_1\in L\land s_2\in\emptyset\}$$

By definition, $x\notin\emptyset$ for all $x$, so $(s_1\in L)\land (s_2\in \emptyset) \equiv (s_1\in L)\land \bot \equiv \bot$. Hence $L\emptyset=\{s_1s_2\mid\bot\}=\emptyset$ for any language $L$.

It stands to reason that the identity element of $\mathcal{P}(\Sigma^*)$ would be $E=\{\varepsilon\}$, where $\varepsilon$ is the empty string. This follows from $LE=EL=L$ for all $L\in\mathcal{P}(\Sigma^*)$.


For a more "mathy" take, consider the following:

Claim: If $\mathcal{P}(\Sigma^*)$ with language concatenation is a monoid, then $E=\{\varepsilon\}$ is the identity element.

proof-sketch: By definition, if $M$ is a monoid, then $M$ contains a unique identity element $e$ satisfying $xe=ex=x$ for all $x\in M$. Observe that for all $s\in\Sigma$, $s\varepsilon=\varepsilon s=s$ where $\varepsilon$ is the empty string.

If $E=\{\varepsilon\}$ is the language containing the empty string, then for all $L\in\mathcal{P}(\Sigma^*)$...

$$LE=\{le\mid l\in L\land e\in E\}=\{l\varepsilon\mid l\in L\}=\{l\mid l\in L\}=L$$

...and...

$$EL=\{el\mid e\in E\land l\in L\}=\{\varepsilon l\mid l\in L\}=\{l\mid l\in L\}=L$$

Whence...

$$LE=EL=L$$

Thus, $E$ is the unique identity of the monoid $P(\Sigma^*)$. Q.E.D.

$\endgroup$
2
1
$\begingroup$

This is not a specific property of free monoids, it holds for any monoid. More precisely, take a monoid $M$ with identity $1$. Then ${\cal P}(M)$, the power set of $M$ is a monoid under the product defined, for each $S,T \in {\cal P}(M)$ by $$ ST = \{st \mid s \in S, t \in T\} $$ The identity of ${\cal P}(M)$ is the singleton $\{1\}$, since, according to the definition of the product $$ S\{1\} = \{st \mid s \in S, t \in \{1\} \} = \{s1 \mid s \in S\} = S $$ and $\{1\}S = S$ by a dual argument. The empty set is a zero of the monoid ${\cal P}(M)$. Indeed $$ S \emptyset = \{st \mid s \in S, t \in \emptyset\} = \emptyset $$ and $\emptyset S = \emptyset$ by a dual argument.

$\endgroup$
2
  • $\begingroup$ Thanks. Given a monoid M, does the product of two subsets S and T of M belong to P(M)? Is the product the same or different from Cartesian product of two sets? I guess yes, and think that the Cartesian product of two subsets of M doesn't belong to P(M) but to P(M*M). $\endgroup$ – Tim Jun 24 '20 at 9:45
  • $\begingroup$ Yes, $ST$ belongs to ${\cal P}(M)$ and $S \times T$ to ${\cal P}(M \times M)$. $\endgroup$ – J.-E. Pin Jun 24 '20 at 9:59

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.