hws/hw03.tex
changeset 517 edab48a5b37e
parent 444 3056a4c071b0
child 577 7a437f1f689d
--- 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)