Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
strings_and_languages [2009/04/28 20:38] vkuncak |
strings_and_languages [2019/07/02 16:16] (current) fabien [Strings and languages] |
||
---|---|---|---|
Line 18: | Line 18: | ||
\end{eqnarray*} | \end{eqnarray*} | ||
Therefore, $(\Sigma^*, {\ \cdot\ }, \epsilon)$ is a [[monoid]]. | Therefore, $(\Sigma^*, {\ \cdot\ }, \epsilon)$ is a [[monoid]]. | ||
- | |||
- | We sometimes omit $\cdot$ and write $w_1 \cdot w_2$ simply as $w_1 w_2$. | ||
If $w$ is a word, we define $w^0 = \epsilon$ and $w^{n+1} = w \cdot w^n$. | If $w$ is a word, we define $w^0 = \epsilon$ and $w^{n+1} = w \cdot w^n$. | ||
Line 34: | Line 32: | ||
L^* &=& \bigcup_{n \geq 0} L^n = \{ w_1 \ldots w_n \mid w_1,\ldots,w_n \in L \} | L^* &=& \bigcup_{n \geq 0} L^n = \{ w_1 \ldots w_n \mid w_1,\ldots,w_n \in L \} | ||
\end{eqnarray*} | \end{eqnarray*} | ||
+ | |||
+ | ==== Simple Consequences ==== | ||
+ | |||
+ | Observe that | ||
+ | \begin{equation*} | ||
+ | \emptyset \cdot L = \{ s_1 \cdot s_2 \mid s_1 \in \emptyset \land s_2 \in L \} = \{s_1 \cdot s_2 \mid \mbox{false} \} = \emptyset | ||
+ | \end{equation*} | ||
+ | Similarly, $L \cdot \emptyset = \emptyset$. | ||
+ | |||
+ | Also directly from definition follows: | ||
+ | \begin{equation*} | ||
+ | \{ w_1 \} \cdot \{ w_2 \} = \{ w_1\cdot w_2 \} | ||
+ | \end{equation*} | ||
+ | |||