
diff -r 92e6985018ae -r 4deef8ac5d72 hws/hw04.tex
--- a/hws/hw04.tex	Mon Sep 29 00:45:38 2014 +0100
+++ b/hws/hw04.tex	Sun Oct 05 23:56:18 2014 +0100
@@ -1,13 +1,11 @@
 \documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
+
 \usepackage{tikz}
 \usetikzlibrary{automata}
 
 
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 
 \begin{document}
 
@@ -21,6 +19,21 @@
 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$,  
 is it possible for $L(r)$ to be empty?
 
+\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 $(a + 3) * b$
+  \item $)()++ -33$
+  \item $(a / 3) * 3$
+\end{itemize}
+
+In case they can, can you give the corresponding token
+sequences.
+
 \item Assume that $s^{-1}$ stands for the operation of reversing a
 string $s$. Given the following \emph{reversing} function on regular 
 expressions
@@ -67,48 +80,6 @@
 that can recognise any character, and a regular expression \texttt{NOT} that recognises
 the complement of a regular expression.)
 
-\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say  $q_0$ and $q_1$.
-The starting state is $q_0$ and the final state is $q_1$. The transition
-function is given by
-
-\begin{center}
-\begin{tabular}{l}
-$(q_0, a) \rightarrow q_0$\\
-$(q_0, b) \rightarrow q_1$\\
-$(q_1, b) \rightarrow q_1$
-\end{tabular}
-\end{center}
-
-What is the languages recognised by this automaton?
-
-\item Give a non-deterministic finite automaton that can recognise 
-the language $L(a\cdot (a + b)^* \cdot c)$. 
-
-
-\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
-find the corresponding minimal automaton. In case states can be merged,
-state clearly which states can
-be merged.
-
-\begin{center}
-\begin{tikzpicture}[scale=3, line width=0.7mm]
-  \node[state, initial]        (q0) at ( 0,1) {$q_0$};
-  \node[state]                    (q1) at ( 1,1) {$q_1$};
-  \node[state, accepting] (q4) at ( 2,1) {$q_4$};
-  \node[state]                    (q2) at (0.5,0) {$q_2$};
-  \node[state]                    (q3) at (1.5,0) {$q_3$};
-  \path[->] (q0) edge node[above] {$0$} (q1)
-                  (q0) edge node[right] {$1$} (q2)
-                  (q1) edge node[above] {$0$} (q4)
-                  (q1) edge node[right] {$1$} (q2)
-                  (q2) edge node[above] {$0$} (q3)
-                  (q2) edge [loop below] node {$1$} ()
-                  (q3) edge node[left] {$0$} (q4)
-                  (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
-                  (q4) edge [loop right] node {$0, 1$} ()
-                  ;
-\end{tikzpicture}
-\end{center}
 
 
 %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
@@ -124,7 +95,7 @@
 % explain what is a context-free grammar and the language it generates 
 %
 %
-% Define the language L(M) accepted by a deterministic finite automaton M.
+% 
 %
 %
 % does (a + b)*b+ and (a*b+) + (b*b+) define the same language




