Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
strings_and_languages [2007/05/05 19:17] vkuncak |
strings_and_languages [2009/04/28 20:39] vkuncak |
||
---|---|---|---|
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 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 30: | Line 32: | ||
L^0 &=& \{ \epsilon \} \\ | L^0 &=& \{ \epsilon \} \\ | ||
L^{n+1} &=& L \cdot L^n \\ | L^{n+1} &=& L \cdot L^n \\ | ||
- | L^* &=& \bigcup_{n \geq 0} L^n | + | L^* &=& \bigcup_{n \geq 0} L^n = \{ w_1 \ldots w_n \mid w_1,\ldots,w_n \in L \} |
\end{eqnarray*} | \end{eqnarray*} | ||