\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 $zeroable$ which takes a regular expression as argument
and returns a boolean. The 
function should satisfy the following property:
\begin{center}
$zeroable(r)$ \;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 \texttt{"}$(a + 3) * b$\texttt{"}
\item \texttt{"}$)()++ -33$\texttt{"}
\item \texttt{"}$(a / 3) * 3$\texttt{"}
\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: