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