diff -r e85600529ca5 -r 4794759139ea hw03.tex --- a/hw03.tex Sat Jun 15 09:11:11 2013 -0400 +++ /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: