# HG changeset patch
# User cu
# Date 1507726133 -3600
# Node ID edab48a5b37e7599abd7d86094e990ab6804e800
# Parent  ff643cbb7142f394a7e88a8c1604f2130c3acceb
updated

diff -r ff643cbb7142 -r edab48a5b37e hws/hw03.pdf
Binary file hws/hw03.pdf has changed
diff -r ff643cbb7142 -r edab48a5b37e hws/hw03.tex
--- a/hws/hw03.tex	Tue Oct 10 18:53:30 2017 +0100
+++ b/hws/hw03.tex	Wed Oct 11 13:48:53 2017 +0100
@@ -37,14 +37,14 @@
   \end{center}
 
 \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
+  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$
+      $(Q_0, a) \rightarrow Q_0$\\
+      $(Q_0, b) \rightarrow Q_1$\\
+      $(Q_1, b) \rightarrow Q_1$
     \end{tabular}
   \end{center}
 
@@ -53,7 +53,7 @@
 \item Give a non-deterministic finite automaton that can
       recognise the language $L(a\cdot (a + b)^* \cdot c)$.
 
-\item Given a deterministic finite automaton $A(Q, q_0, F,
+\item Given a deterministic finite automaton $A(\varSigma, Q, Q_0, F,
       \delta)$, define which language is recognised by this
       automaton. Can you define also the language defined by a
       non-deterministic automaton?
@@ -70,8 +70,8 @@
                         every state/.style={minimum size=0pt,
                         inner sep=2pt,draw=blue!50,very thick,
                         fill=blue!20},scale=2]
-      \node[state, initial]        (q0) at ( 0,1) {$q_0$};
-      \node[state, accepting]  (q1) at ( 1,1) {$q_1$};
+      \node[state, initial]        (q0) at ( 0,1) {$Q_0$};
+      \node[state, accepting]  (q1) at ( 1,1) {$Q_1$};
       \path[->] (q0) edge node[above] {$a$} (q1)
                 (q1) edge [loop right] node {$b$} ();
     \end{tikzpicture}
@@ -106,9 +106,9 @@
                         every state/.style={minimum size=0pt,
                         inner sep=2pt,draw=blue!50,very thick,
                         fill=blue!20},scale=2]
-      \node[state, initial]        (q0) at ( 0,1) {$q_0$};
-      \node[state]                    (q1) at ( 1,1) {$q_1$};
-      \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+      \node[state, initial]        (q0) at ( 0,1) {$Q_0$};
+      \node[state]                    (q1) at ( 1,1) {$Q_1$};
+      \node[state, accepting] (q2) at ( 2,1) {$Q_2$};
       \path[->] (q0) edge node[above] {$a$} (q1)
                 (q0) edge [loop above] node[above] {$b$} ()
                 (q0) edge [loop below] node[below] {$a$} ()
@@ -116,7 +116,8 @@
     \end{tikzpicture}
   \end{center}
 
-\item Given the following deterministic finite automaton over the
+\item \textbf{(Deleted for 2017)}
+  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.
 
@@ -125,11 +126,11 @@
                         every state/.style={minimum size=0pt,
                         inner sep=2pt,draw=blue!50,very thick,
                         fill=blue!20},scale=2]
-      \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$};
+      \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)
@@ -149,9 +150,9 @@
                         every state/.style={minimum size=0pt,
                         inner sep=2pt,draw=blue!50,very thick,
                         fill=blue!20}]
-      \node[state, initial, accepting]        (q0) at ( 0,1) {$q_0$};
-      \node[state, accepting]                    (q1) at ( 1,1) {$q_1$};
-      \node[state] (q2) at ( 2,1) {$q_2$};
+      \node[state, initial, accepting]        (q0) at ( 0,1) {$Q_0$};
+      \node[state, accepting]                    (q1) at ( 1,1) {$Q_1$};
+      \node[state] (q2) at ( 2,1) {$Q_2$};
       \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
                 (q1) edge[bend left] node[above] {$b$} (q0)
                 (q2) edge[bend left=50] node[below] {$b$} (q0)
diff -r ff643cbb7142 -r edab48a5b37e progs/re3.scala
--- a/progs/re3.scala	Tue Oct 10 18:53:30 2017 +0100
+++ b/progs/re3.scala	Wed Oct 11 13:48:53 2017 +0100
@@ -1,6 +1,7 @@
 // Version with simplification during derivatives;
 // this keeps the regular expressions small, which
 // is good for run-time
+ 
 
 abstract class Rexp
 case object ZERO extends Rexp
diff -r ff643cbb7142 -r edab48a5b37e slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r ff643cbb7142 -r edab48a5b37e slides/slides03.tex
--- a/slides/slides03.tex	Tue Oct 10 18:53:30 2017 +0100
+++ b/slides/slides03.tex	Wed Oct 11 13:48:53 2017 +0100
@@ -407,7 +407,7 @@
 Whether a string \bl{$s$} is accepted by \bl{$A$}?
 
 \begin{center}
-\hspace{5mm}\bl{$\hat{\delta}(\mbox{Q}_0, s) \in F$}
+\hspace{5mm}\bl{$\widehat{\delta}(\mbox{Q}_0, s) \in F$}
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -708,7 +708,7 @@
 
 \small
 \mbox{}\\\medskip
-We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
+We can just put both automata together.
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%