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 [2007/05/05 19:17] vkuncak |
strings_and_languages [2019/07/02 16:16] fabien [Strings and languages] |
||
|---|---|---|---|
| Line 10: | Line 10: | ||
| \end{equation*} | \end{equation*} | ||
| - | We use centered dot for string concatenation, as in $s_1 \cdot s_2$, and we sometimes omit it, as in $s_1 s_2$ (programming language Objective Caml uses ^ to denote string concatenation; other languages often use + as an overloaded operator, but we will not use + for concatentation). | + | We use centered dot for string concatenation, as in $s_1 \cdot s_2$, and we sometimes omit it, as in $s_1 s_2$ (programming language Objective Caml uses ^ to denote string concatenation; other languages often use + as an overloaded operator). |
| The concatentation is an operation $\Sigma^* \times \Sigma^* \to \Sigma^*$. It is associative, and $\epsilon$ is left and right neutral element: | The concatentation is an operation $\Sigma^* \times \Sigma^* \to \Sigma^*$. It is associative, and $\epsilon$ is left and right neutral element: | ||
| Line 32: | 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*} | ||
| + | |||