diff -r 4758a6155878 -r 1ab41c59e3d3 hw/hw03.tex --- a/hw/hw03.tex Thu Sep 26 10:39:23 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -\documentclass{article} -\usepackage{charter} -\usepackage{hyperref} -\usepackage{amssymb} -\usepackage{amsmath} - -\begin{document} - -\section*{Homework 3} - -\begin{enumerate} -\item Assume you have an alphabet consisting of the letters $a$, $b$ and $c$ only. -(a) Find a regular expression that recognises the two strings $ab$ and $ac$. (b) -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.\footnote{In an earlier version there was an error.} 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: