\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}

\begin{document}

\section*{Homework 3}

\begin{enumerate}
\item What is a regular language?

\item Assume you have an alphabet consisting of the letters
      $a$, $b$ and $c$ only. (1) Find a regular expression
      that recognises the two strings $ab$ and $ac$. (2) Find
      a regular expression that matches all strings
      \emph{except} these two strings. Note, you can only use
      regular expressions of the form 
      
      \begin{center} $r ::=
      \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
      r_1 \cdot r_2 \;|\; r^*$ 
      \end{center}

\item Define the function \textit{zeroable} which takes a
      regular expression as argument and returns a boolean.
      The function should satisfy the following property:

\begin{center}
$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
\end{center}

\item Define the tokens and regular expressions for a language
      consisting of numbers, left-parenthesis $($,
      right-parenthesis $)$, identifiers and the operations $+$,
      $-$ and $*$. Can the following strings in this language
      be lexed?

\begin{itemize}
  \item $(a + 3) * b$
  \item $)()++ -33$
  \item $(a / 3) * 3$
\end{itemize}

In case they can, can you give the corresponding token
sequences.

\end{enumerate}



\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: