handouts/ho01.tex
changeset 111 1933e88cb73e
parent 110 9353308f1c6a
child 112 95ee5cc5c05d
equal deleted inserted replaced
110:9353308f1c6a 111:1933e88cb73e
   218 these kind of not-regular-expressions is. Try to write down the regular expression which can match any
   218 these kind of not-regular-expressions is. Try to write down the regular expression which can match any
   219 string except {\it "hello"} and {\it "world"}. It is possible in principle, but often it is easier to just include
   219 string except {\it "hello"} and {\it "world"}. It is possible in principle, but often it is easier to just include
   220 $\sim{}r$ in the definition or regular expressions. Whenever we do so, we will state it explicitly.
   220 $\sim{}r$ in the definition or regular expressions. Whenever we do so, we will state it explicitly.
   221 
   221 
   222 So far we have only considered informally what the \emph{meaning} of a regular expression is.  
   222 So far we have only considered informally what the \emph{meaning} of a regular expression is.  
   223 Formally, we associate with every regular expression a set of strings which are matched by this
   223 To do so more formally we will associate with every regular expression a set of strings 
   224 regular expression. This can be formally defined as 
   224 that is supposed to be  are matched by this
       
   225 regular expression. This can be defined recursively  as follows
   225 
   226 
   226 \begin{center}
   227 \begin{center}
   227 \begin{tabular}{rcl}
   228 \begin{tabular}{rcl}
   228 $L(\varnothing)$  & $\dn$ & $\{\,\}$\\
   229 $L(\varnothing)$  & $\dn$ & $\{\,\}$\\
   229 $L(\epsilon)$       & $\dn$ & $\{""\}$\\
   230 $L(\epsilon)$       & $\dn$ & $\{""\}$\\