diff -r 70c307641d05 -r 1e4da6d2490c hws/hw03.tex --- a/hws/hw03.tex Mon Sep 22 13:42:14 2014 +0100 +++ b/hws/hw03.tex Fri Sep 26 14:06:55 2014 +0100 @@ -11,34 +11,41 @@ \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 +\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} -$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$ +$\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? + 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{"} + \item $(a + 3) * b$ + \item $)()++ -33$ + \item $(a / 3) * 3$ \end{itemize} +In case they can, can you give the corresponding token +sequences. -In case they can, can you give the corresponding token sequences. \end{enumerate}