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 18:38] vkuncak |
strings_and_languages [2012/09/19 16:55] vkuncak |
||
|---|---|---|---|
| Line 18: | Line 18: | ||
| \end{eqnarray*} | \end{eqnarray*} | ||
| Therefore, $(\Sigma^*, {\ \cdot\ }, \epsilon)$ is a [[monoid]]. | Therefore, $(\Sigma^*, {\ \cdot\ }, \epsilon)$ is a [[monoid]]. | ||
| + | |||
| + | If $w$ is a word, we define $w^0 = \epsilon$ and $w^{n+1} = w \cdot w^n$. | ||
| A **language** is any set of strings, that is, a set $L \subseteq \Sigma^*$. | A **language** is any set of strings, that is, a set $L \subseteq \Sigma^*$. | ||
| Line 28: | Line 30: | ||
| 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*} | ||
| + | |||
| + | ==== Simple Consequences ==== | ||
| + | |||
| + | Observe that | ||
| + | \[ | ||
| + | \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 | ||
| + | \] | ||
| + | Similarly, $L \cdot \emptyset = \emptyset$. | ||
| + | |||
| + | Of course, $\{ w_1 \} \cdot \{ w_2 \} = w_1\cdot w_2$. | ||