--- a/hws/hw03.tex Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw03.tex Fri Oct 10 16:59:22 2014 +0100
@@ -7,77 +7,146 @@
\section*{Homework 3}
\begin{enumerate}
-\item What is a regular language?
+\item What is a regular language? Are there alternative ways to define this
+ notion? If yes, give an explanation why they define the same notion.
+
+\item Why is every finite set of strings a regular language?
-\item Assume you have an alphabet consisting of the letters
- $a$, $b$ and $c$ only. (1) Find a regular expression
- that recognises the two strings $ab$ and $ac$. (2) Find
- a regular expression that matches all strings
- \emph{except} these two strings. Note, you can only use
- regular expressions of the form
+\item Assume you have an alphabet consisting of the letters $a$, $b$
+ and $c$ only. (1) Find a regular expression that recognises the two
+ strings $ab$ and $ac$. (2) Find a regular expression that matches
+ all strings \emph{except} these two strings. Note, you can only use
+ regular expressions of the form
- \begin{center} $r ::=
- \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
- r_1 \cdot r_2 \;|\; r^*$
- \end{center}
+ \begin{center} $r ::=
+ \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\;
+ r_1 \cdot r_2 \;|\; r^*$
+ \end{center}
+
+\item Define the function \textit{zeroable} which takes a regular
+ expression as argument and returns a boolean. The function should
+ satisfy the following property:
+
+ \begin{center}
+ $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
+ \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
-\item Define the function \textit{zeroable} which takes a
- regular expression as argument and returns a boolean.
- The function should satisfy the following property:
+ \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}
-\begin{center}
-$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
-\end{center}
+ What is the language 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 a deterministic finite automata $A(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?
-\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
+\item Given the following deterministic finite automata over the
+ alphabet $\{a, b\}$, find an automaton that recognises the
+ complement language. (Hint: Recall that for the algorithm from the
+ lectures, the automaton needs to be in completed form, that is have
+ a transition for every letter from the alphabet.)
-\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}
+ \begin{center}
+ \begin{tikzpicture}[scale=2, line width=0.7mm]
+ \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}
+ \end{center}
+
+\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.
-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)$.
+ \begin{center}
+ \begin{tikzpicture}[scale=2, 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 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.
+%\item Given the following deterministic finite automaton
+%
+%\begin{center}
+%\begin{tikzpicture}[scale=3, line width=0.7mm]
+% \node[state, initial] (q0) at ( 0,1) {$q_0$};
+% \node[state,accepting] (q1) at ( 1,1) {$q_1$};
+% \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+% \path[->] (q0) edge node[above] {$b$} (q1)
+% (q1) edge [loop above] node[above] {$a$} ()
+% (q2) edge [loop above] node[above] {$a, b$} ()
+% (q1) edge node[above] {$b$} (q2)
+% (q0) edge[bend right] node[below] {$a$} (q2)
+% ;
+%\end{tikzpicture}
+%\end{center}
+%find the corresponding minimal automaton. State clearly which nodes
+%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 Given the following non-deterministic finite automaton over the
+ alphabet $\{a, b\}$, find a deterministic finite automaton that
+ recognises the same language:
+
+ \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] (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$} ()
+ (q1) edge node[above] {$a$} (q2);
+ \end{tikzpicture}
+ \end{center}
+
+\item Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
-\item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.
+ \begin{center}
+ \begin{tikzpicture}[scale=2, line width=0.5mm]
+ \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)
+ (q1) edge node[above] {$a$} (q2)
+ (q2) edge [loop right] node {$a$} ()
+ (q0) edge [loop below] node {$b$} ()
+ ;
+ \end{tikzpicture}
+ \end{center}
+ Give a regular expression that can recognise the same language as
+ 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^*$.)
\end{enumerate}
-
-
\end{document}
%%% Local Variables: