equal
deleted
inserted
replaced
230 \end{tabular} |
230 \end{tabular} |
231 \end{center} |
231 \end{center} |
232 |
232 |
233 \noindent Note the difference in the last two lines: the empty |
233 \noindent Note the difference in the last two lines: the empty |
234 set behaves like $0$ for multiplication and the set $\{[]\}$ |
234 set behaves like $0$ for multiplication and the set $\{[]\}$ |
235 like $1$ for multiplication. |
235 like $1$ for multiplication ($n * 1 = n$ and $n * 0 = 0$). |
236 |
236 |
237 Following the language concatenation, we can define a |
237 Following the language concatenation, we can define a |
238 \defn{language power} operation as follows: |
238 \defn{language power} operation as follows: |
239 |
239 |
240 \begin{eqnarray*} |
240 \begin{eqnarray*} |
245 \noindent This definition is by recursion on natural numbers. |
245 \noindent This definition is by recursion on natural numbers. |
246 Note carefully that the zero-case is not defined as the empty |
246 Note carefully that the zero-case is not defined as the empty |
247 set, but the set containing the empty string. So no matter |
247 set, but the set containing the empty string. So no matter |
248 what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is |
248 what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is |
249 another hint about a connection between the $@$-operation and |
249 another hint about a connection between the $@$-operation and |
250 multiplication: How is $x^n$ defined and what is $x^0$?) |
250 multiplication: How is $x^n$ defined recursively and what is |
251 |
251 $x^0$?) |
252 Next we can define the \defn{star operation} for languages: |
252 |
|
253 Next we can define the \defn{star operation} for languages: |
253 $A^*$ is the union of all powers of $A$, or short |
254 $A^*$ is the union of all powers of $A$, or short |
254 |
255 |
255 \begin{equation}\label{star} |
256 \begin{equation}\label{star} |
256 A^* \dn \bigcup_{0\le n}\; A^n |
257 A^* \dn \bigcup_{0\le n}\; A^n |
257 \end{equation} |
258 \end{equation} |