--- a/hw/hw05.tex Thu Sep 26 10:39:23 2013 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,116 +0,0 @@
-\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: