Binary file hws/hw01.pdf has changed

--- a/hws/hw01.tex	Sat Nov 01 15:06:41 2014 +0000
+++ b/hws/hw01.tex	Sat Nov 01 16:19:05 2014 +0000
@@ -42,7 +42,9 @@
 \item How is the power of a language defined? (Hint: There are two
   rules, one for $\_^0$ and one for $\_^{n+1}$.)
 
-\item Let $A = \{[], [a], [b], [c]\}$. How many strings are in $A^4$?
+\item Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$?
+  Consider the case of $A^4$ where one of the strings in $A$ is the 
+  empty string.
 
 \item How many regular expressions are there to match the string
   $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?

Binary file hws/hw02.pdf has changed

--- a/hws/hw02.tex	Sat Nov 01 15:06:41 2014 +0000
+++ b/hws/hw02.tex	Sat Nov 01 16:19:05 2014 +0000
@@ -69,6 +69,32 @@
 
 \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define 
   the same language?
+
+\item Define the function $zeroable$ by recursion over regular
+  expressions. This function should satisfy the property
+
+  \[
+  zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*)
+  \]
+
+  The function $nullable$ for the not-regular expressions can be defined
+  by 
+
+  \[
+  nullable(\sim r) \dn \neg(nullable(r))
+  \]
+
+  Unfortunately, a similar definition for $zeroable$ does not satisfy
+  the property in $(*)$:
+
+  \[
+  zeroable(\sim r) \dn \neg(zeroable(r))
+  \]
+
+  Find out why?
+
+\item Give a regular expressions that can recognise all strings from the 
+  language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$.
 \end{enumerate}
 
 \end{document}

Binary file hws/hw03.pdf has changed

--- a/hws/hw03.tex	Sat Nov 01 15:06:41 2014 +0000
+++ b/hws/hw03.tex	Sat Nov 01 16:19:05 2014 +0000
@@ -159,6 +159,12 @@
   this automaton. (Hint: If you use Brzozwski's method, you can assume
   Arden's lemma which states that an equation of the form $q = q\cdot r + s$
   has the unique solution $q = s \cdot r^*$.)
+
+\item If a non-deterministic finite automaton (NFA) has
+$n$ states. How many states does a deterministic 
+automaton (DFA) that can recognise the same language
+as the NFA maximal need?
+
 \end{enumerate}
 
 \end{document}

Binary file hws/hw04.pdf has changed

--- a/hws/hw04.tex	Sat Nov 01 15:06:41 2014 +0000
+++ b/hws/hw04.tex	Sat Nov 01 16:19:05 2014 +0000
@@ -67,7 +67,11 @@
   that can recognise any character, and a regular expression \texttt{NOT} that recognises
   the complement of a regular expression.)
 
-
+\item How many basic regular expressions are there to match the string
+  $abcd$? (ii) How many if they cannot include $\epsilon$ and
+  $\varnothing$? (iii) How many if they are also not allowed to
+  contain stars? (iv) How many if they are also not allowed to contain
+  $\_ + \_$?
 
 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
 %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so 

Binary file hws/hw05.pdf has changed

--- a/hws/hw05.tex	Sat Nov 01 15:06:41 2014 +0000
+++ b/hws/hw05.tex	Sat Nov 01 16:19:05 2014 +0000
@@ -12,6 +12,42 @@
 \section*{Homework 5}
 
 \begin{enumerate}
+\item Consider the basic regular expressions
+
+\begin{center}
+$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
+\end{center}
+
+and suppose you want to show a property $P(r)$ for all regular
+expressions $r$ by structural induction. Write down which cases do you 
+need to analyse. State clearly the induction hypotheses if applicable
+in a case.
+
+\item Define a regular expression, written $ALL$, that can match 
+every string. This definition should be in terms of the
+following extended regular expressions:
+
+\begin{center}
+$r ::= \varnothing \;|\; 
+       \epsilon \;|\;  
+       c  \;|\; 
+       r_1 + r_2 \;|\; 
+       r_1 \cdot r_2 \;|\; 
+       r^* \;|\;
+       \sim r$
+\end{center}
+
+\item Assume the delimiters for comments are \texttt{$\slash$*}
+and \texttt{*$\slash$}. Give a regular expression that can
+recognise comments of the form
+
+\begin{center}
+\texttt{$\slash$*~\ldots{}~*$\slash$} 
+\end{center}
+
+where the three dots stand for arbitrary characters, but not
+comment delimiters.
+
 \item Define the following regular expressions 
 
 \begin{center}
@@ -24,15 +60,32 @@
 \end{tabular}
 \end{center}
 
-in terms of the usual regular expressions
+in terms of the usual basic regular expressions
 
 \begin{center}
 $r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
 \end{center}
 
+\item Give the regular expressions for lexing a language
+consisting of identifiers, left-parenthesis \texttt{(},
+right-parenthesis \texttt{)}, numbers that can be either
+positive or negative, and the operations \texttt{+},
+\texttt{-} and \texttt{*}. 
 
+Decide whether the following strings 
+can be lexed in this language?
 
-\item Recall the definitions for $Der$ and $der$ from the lectures. 
+\begin{enumerate}
+\item \texttt{"(a3+3)*b"}
+\item \texttt{")()++-33"}
+\item \texttt{"(b42/3)*3"}
+\end{enumerate}
+
+In case they can, give the corresponding token sequences. (Hint: 
+Observe the maximal munch rule and the priorities of your regular
+expressions that make the process of lexing unambiguous.)
+
+\item (Optional) Recall the definitions for $Der$ and $der$ from the lectures. 
 Prove by induction on $r$ the property that 
 
 \[
@@ -40,6 +93,7 @@
 \]
 
 holds.
+
 \end{enumerate}
 
 \end{document}

Binary file hws/hw06.pdf has changed