\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 regularexpressions $r$ by structural induction. Write down which cases do you need to analyse. State clearly the induction hypotheses if applicablein a case.\item Define a regular expression, written $ALL$, that can match every string. This definition should be in terms of thefollowing 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 languageconsisting of identifiers, left-parenthesis \texttt{(},right-parenthesis \texttt{)}, numbers that can be eitherpositive 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 regularexpressions 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: