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