\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}

\solution{
  There is the obvious solution $\sim{}\ZERO$, but also $a + \sim{}a$ would work.
}  
     

%\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 The \emph{not}-regular expression is definitely useful for recognising
  comments for example, but can
  sometimes be quite unintuitive when it comes to deciding which strings are
  matched or not. Consider

  \[
  (\sim{}a)^*  \quad\text{and}\quad \sim{}(a^*)\;.  
  \]  

  What is the language of each regular expression?

  \solution{
    The first one is ``all strings, except $[a]$''; the second
    ``all strings except strings of the form $a^*$''.
  }
  
\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}

\solution{
  $r^+ \dn r\cdot r^*$\\
  $r^? \dn r + 1$\\
  $r^{\{0\}} = \ONE$\\
  $r^{\{n\}} \dn r\cdot r^{\{n-1\}}$\\
  $r^{\{..n\}} \dn (r^?)^{\{n\}}$\\
  $r^{\{n..m\}} \dn r^{\{..m-n\}}\cdot r^{\{n\}}$\\

  BTW, $r^{\{n..m\}}$ cannot be defined in terms of $r^{\{n..\}} \;\&\; r^{\{..m\}}$ where $\&$ is
  the intersection operator I introduced this year. For example assume $r=aaa + aaaaaaa$, then 
  $r^{\{4..6\}}$ cannot match 21 a's, but $r^{\{4..\}} \;\&\; r^{\{..6\}}$.
  }


\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.)

\solution{
  The first two strings can be lexed. But not the last ($/$ is not part of the language).
}

\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}

\solution{
  The first and the last cannot be matched. Maybe it is a good exercise to
  write down the derivations for the rest.

  BTW, the language recognised by this grammar is strings consisting of
  a's and b's where there are equal or more number of b's than a's (including the
  empty string).
}

\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.

\solution{Palindromes with the same number of a's and b's, including
  the empty string}


\item Remember we have specified identifiers with regular expressions as
  strings that start with a letter followed by letters, digits and
  underscores. This can also be specified by a grammar rule or rules.
  What would the rule(s) look like for identifiers? 

  \solution{
  \begin{plstx}[margin=1cm]
  : \meta{Id\/} ::= \meta{Let\/}\cdot \meta{R}\\
  : \meta{Let\/} ::= a \;\mid\; \dots \;\mid\; z\\
  : \meta{Dig\/} ::= 0 \;\mid\; \dots \;\mid\; 9\\
  : \meta{R\/} ::= \meta{Let\/} \cdot \meta{R\/} \;\mid\;
                  \meta{Dig\/} \cdot \meta{R\/} \;\mid\;
                  $\_$ \cdot \meta{R\/} \;\mid\; \epsilon\\
  \end{plstx}  
}

\item If we specify keywords, identifiers (see above) and programs
  by grammar rules, are there any problems you need to be careful
  about when using a parser for identifying tokens?

  \solution{Parsers do not have the POSIX rules (e.g.~longest munch
    rule) built in. I am not aware that any parser does this out of
    the box and you would need to build in such constraints into the
    grammar rules or parsing mechanism.}

\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: 
