--- 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)