\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../graphics}+ −
\usepackage{../grammar}+ −
+ −
\begin{document}+ −
+ −
% explain what is a context-free grammar and the language it generates + −
%+ −
+ −
+ −
\section*{Homework 5}+ −
+ −
\HEADER+ −
+ −
+ −
\begin{enumerate}+ −
\item Consider the basic regular expressions+ −
+ −
\begin{center}+ −
$r ::= \ZERO \;|\; \ONE \;|\; 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 ::= \ZERO \;|\; + −
\ONE \;|\; + −
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 ::= \ZERO \;|\; \ONE \;|\; 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 Suppose the following context-free grammar $G$+ −
+ −
\begin{plstx}[margin=1cm]+ −
: \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\;+ −
\meta{B\/}\cdot\meta{S\/}\cdot\meta{A\/} \;\mid\; \epsilon\\+ −
: \meta{A\/} ::= a \mid \epsilon\\+ −
: \meta{B\/} ::= b\\+ −
\end{plstx}+ −
+ −
where the starting symbol is $\meta{S}$.+ −
Which of the following strings are in the language of $G$?+ −
+ −
\begin{itemize}+ −
\item[$\bullet$] $a$+ −
\item[$\bullet$] $b$+ −
\item[$\bullet$] $ab$+ −
\item[$\bullet$] $ba$+ −
\item[$\bullet$] $bb$+ −
\item[$\bullet$] $baa$+ −
\end{itemize}+ −
+ −
\item Suppose the following context-free grammar + −
+ −
\begin{plstx}[margin=1cm]+ −
: \meta{S\/} ::= a\cdot \meta{S\/}\cdot a\;\mid\;+ −
b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\+ −
\end{plstx}+ −
+ −
Describe which language is generated by this grammar.+ −
+ −
+ −
+ −
\item {\bf(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.+ −
+ −
\item \POSTSCRIPT + −
\end{enumerate}+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −