\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}


\begin{document}

% explain what is a context-free grammar and the language it generates 
%


\section*{Homework 5}

\begin{enumerate}
\item Define the following regular expressions 

\begin{center}
\begin{tabular}{ll}
$r^+$ & (one or more matches)\\
$r^?$   & (zero or one match)\\
$r^{\{n\}}$ & (exactly $n$ matches)\\
$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
&  \phantom{(}assumption $m \le n$)\\
\end{tabular}
\end{center}

in terms of the usual regular expressions

\begin{center}
$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
\end{center}



\item Recall the definitions for $Der$ and $der$ from the lectures. 
Prove by induction on $r$ the property that 

\[
L(der\,c\,r) = Der\,c\,(L(r))
\]

holds.
\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: