diff -r e85600529ca5 -r 4794759139ea hw/hw05.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw/hw05.tex	Sat Jun 15 09:23:18 2013 -0400
@@ -0,0 +1,116 @@
+\documentclass{article}
+\usepackage{charter}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{tikz}
+\usetikzlibrary{automata}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+\begin{document}
+
+\section*{Homework 5}
+
+\begin{enumerate}
+\item Define the following regular expressions 
+
+\begin{center}
+\begin{tabular}{ll}
+$r^+$ & (one or more matches)\\
+$r^?$   & (zero or one match)\\
+$r^{\{n\}}$ & (exactly $n$ matches)\\
+$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
+&  \phantom{(}assumption $m \le n$)\\
+\end{tabular}
+\end{center}
+
+in terms of the usual regular expressions
+
+\begin{center}
+$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
+\end{center}
+
+\item Given a deterministic finite automata $A(Q, q_0, F, \delta)$, 
+define which language is recognised by this automaton.
+
+\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{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$};
+  \path[->] (q0) edge node[above] {$a$} (q1)
+                   (q1) edge [loop right] node {$b$} ()
+                  ;
+\end{tikzpicture}
+\end{center}
+
+\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.
+
+\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\}$:
+
+\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: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: