handouts/notation.tex
changeset 242 35104ee14f87
parent 241 10f02605a46a
child 246 baf41b05210f
equal deleted inserted replaced
241:10f02605a46a 242:35104ee14f87
   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}