\documentclass{article}+
−
\usepackage{charter}+
−
\usepackage{hyperref}+
−
\usepackage{amssymb}+
−
\usepackage{amsmath}+
−
\usepackage{tikz}+
−
\usetikzlibrary{automata}+
−
+
−
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions+
−
+
−
\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: +
−