\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 Consider the basic regular expressions

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

and suppose you want to show a property $P(r)$ for all regular
expressions $r$ by structural induction. Write down which cases do you 
need to analyse. State clearly the induction hypotheses if applicable
in a case.

\item Define a regular expression, written $ALL$, that can match 
every string. This definition should be in terms of the
following extended regular expressions:

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

\item Assume the delimiters for comments are \texttt{$\slash$*}
and \texttt{*$\slash$}. Give a regular expression that can
recognise comments of the form

\begin{center}
\texttt{$\slash$*~\ldots{}~*$\slash$} 
\end{center}

where the three dots stand for arbitrary characters, but not
comment delimiters.

\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 basic regular expressions

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

\item Give the regular expressions for lexing a language
consisting of identifiers, left-parenthesis \texttt{(},
right-parenthesis \texttt{)}, numbers that can be either
positive or negative, and the operations \texttt{+},
\texttt{-} and \texttt{*}. 

Decide whether the following strings 
can be lexed in this language?

\begin{enumerate}
\item \texttt{"(a3+3)*b"}
\item \texttt{")()++-33"}
\item \texttt{"(b42/3)*3"}
\end{enumerate}

In case they can, give the corresponding token sequences. (Hint: 
Observe the maximal munch rule and the priorities of your regular
expressions that make the process of lexing unambiguous.)

\item (Optional) 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: