Binary file hws/hw01.pdf has changed
--- a/hws/hw01.tex Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw01.tex Fri Oct 10 16:59:22 2014 +0100
@@ -7,58 +7,51 @@
\begin{enumerate}
-\item {\bf (Optional)} If you want to run the code presented
- in the lectures, install the Scala programming language
- available (for free) from
+\item {\bf (Optional)} If you want to run the code presented in the
+ lectures, install the Scala programming language available (for
+ free) from
\begin{center}
\url{http://www.scala-lang.org}
\end{center}
- If you want to follow the code I present during the
- lectures, read the handout about Scala.
-
-\item {\bf (Optional)} Have a look at the crawler programs.
- Can you find a usage for them in your daily programming
- life? Can you improve them? (For example in cases there
- are links that appear on different recursion levels, the
- crawlers visit such web-pages several times. Can this be
- avoided?)
+ If you want to follow the code I present during the lectures,
+ read the handout about Scala.
-\item Read the handout of the first lecture and the handout
- about notation. Make sure you understand the concepts of
- strings and languages.
+\item {\bf (Optional)} Have a look at the crawler programs. Can you
+ find a usage for them in your daily programming life? Can you
+ improve them? (For example in cases there are links that appear on
+ different recursion levels, the crawlers visit such web-pages
+ several times. Can this be avoided?)
-\item In the context of the AFL-course, what is meant by the
- term \emph{language}?
+\item Read the handout of the first lecture and the handout about
+ notation. Make sure you understand the concepts of strings and
+ languages. In the context of the AFL-course, what is meant by the
+ term \emph{language}?
-\item Give the definition for regular expressions. What is the
- meaning of a regular expression?
+\item Give the definition for regular expressions. What is the meaning
+ of a regular expression? (Hint: The meaning is defined recursively.)
-\item Assume the concatenation operation of two strings is
- written as $s_1 @ s_2$. Define the operation of
- \emph{concatenating}, written $\_ \,@\, \_$ two sets of
- strings.
+\item Assume the concatenation operation of two strings is written as
+ $s_1 @ s_2$. Define the operation of \emph{concatenating}, written
+ $\_ \,@\, \_$ two sets of strings.
-\item Assume a set $A$ contains 4 strings and a set $B$ 7
- strings, how many strings are in $A @ B$?
+\item Assume a set $A$ contains 4 strings and a set $B$ 7 strings, how
+ many strings are in $A \,@\, B$?
-\item How is the power of a language defined? (Hint: There are
- two rules, one for $\_^0$ and one for
- $\_^{n+1}$.)
+\item How is the power of a language defined? (Hint: There are two
+ rules, one for $\_^0$ and one for $\_^{n+1}$.)
-\item How many regular expressions are there to match the
- string $abc$? How many if they cannot include
- $\epsilon$ and $\varnothing$? How many if they are also
- not allowed to contain stars? How many if they are also
- not allowed to contain $\_ + \_$?
+\item How many regular expressions are there to match the string
+ $abc$? How many if they cannot include $\epsilon$ and $\varnothing$?
+ How many if they are also not allowed to contain stars? How many if
+ they are also not allowed to contain $\_ + \_$?
-\item When are two regular expressions equivalent? Can you
- think of instances where two regular expressions match
- the same strings, but it is not so obvious that they do? For
- example $a + b$ and $b + a$ do not count\ldots they
- obviously match the same strings, namely $[a]$ and $[b]$.
-
+\item When are two regular expressions equivalent? Can you think of
+ instances where two regular expressions match the same strings, but
+ it is not so obvious that they do? For example $a + b$ and $b + a$
+ do not count\ldots they obviously match the same strings, namely
+ $[a]$ and $[b]$.
\end{enumerate}
\end{document}
Binary file hws/hw02.pdf has changed
--- a/hws/hw02.tex Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw02.tex Fri Oct 10 16:59:22 2014 +0100
@@ -1,50 +1,44 @@
\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
\begin{document}
\section*{Homework 2}
\begin{enumerate}
-\item Review the first handout about sets of strings and read
- the second handout. Assuming the alphabet is $\{a, b\}$,
- decide which of the following equations are true in
- general for arbitrary languages $A$, $B$ and $C$:
+\item What is the language recognised by the regular expressions
+ $(\varnothing^*)^*$.
-\begin{eqnarray}
-(A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
-A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\
-A^* @ A^* & =^? & A^*\nonumber\\
-(A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber
-\end{eqnarray}
+\item Review the first handout about sets of strings and read the
+ second handout. Assuming the alphabet is the set $\{a, b\}$, decide
+ which of the following equations are true in general for arbitrary
+ languages $A$, $B$ and $C$:
-\noindent In case an equation is true, give an explanation;
-otherwise give a counter-example.
-
-\item What is the meaning of a regular expression? Give an
- inductive definition.
+ \begin{eqnarray}
+ (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
+ A^* \cup B^* & =^? & (A \cup B)^*\nonumber\\
+ A^* @ A^* & =^? & A^*\nonumber\\
+ (A \cap B)@ C & =^? & (A@C) \cap (B@C)\nonumber
+ \end{eqnarray}
-\item Given the regular expressions $r_1 = \epsilon$ and $r_2
- = \varnothing$ and $r_3 = a$. How many strings can the
- regular expressions $r_1^*$, $r_2^*$ and $r_3^*$ each
- match?
+ \noindent In case an equation is true, give an explanation; otherwise
+ give a counter-example.
+\item Given the regular expressions $r_1 = \epsilon$ and $r_2 =
+ \varnothing$ and $r_3 = a$. How many strings can the regular
+ expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
-\item Give regular expressions for (a) decimal numbers and for
- (b) binary numbers. (Hint: Observe that the empty string
- is not a number. Also observe that leading 0s are
- normally not written.)
+\item Give regular expressions for (a) decimal numbers and for (b)
+ binary numbers. (Hint: Observe that the empty string is not a
+ number. Also observe that leading 0s are normally not written.)
\item Decide whether the following two regular expressions are
- equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot
- b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
+ equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot b)^* \cdot
+ a \equiv^? a \cdot (b \cdot a)^*$.
-\item Given the regular expression $r = (a \cdot b + b)^*$.
- Compute what the derivative of $r$ is with respect to
- $a$, $b$ and $c$. Is $r$ nullable?
+\item Given the regular expression $r = (a \cdot b + b)^*$. Compute
+ what the derivative of $r$ is with respect to $a$, $b$ and $c$. Is
+ $r$ nullable?
\item Prove that for all regular expressions $r$ we have
@@ -56,6 +50,25 @@
Write down clearly in each case what you need to prove and
what are the assumptions.
+\item Define what is mean by the derivative of a regular expressions
+ with respoect to a character. (Hint: The derivative is defined
+ recursively.)
+
+\item Assume the set $Der$ is defined as
+
+ \begin{center}
+ $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$
+ \end{center}
+
+ What is the relation between $Der$ and the notion of derivative of
+ regular expressions?
+
+\item Give a regular expression over the alphabet $\{a,b\}$
+ recognising all strings that do not contain any substring $bb$ and
+ end in $a$.
+
+\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define
+ the same language?
\end{enumerate}
\end{document}
Binary file hws/hw03.pdf has changed
--- 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:
--- a/hws/hw04.tex Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw04.tex Fri Oct 10 16:59:22 2014 +0100
@@ -4,81 +4,70 @@
\usepackage{tikz}
\usetikzlibrary{automata}
-
-%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
-
\begin{document}
\section*{Homework 4}
\begin{enumerate}
-\item Why is every finite set of strings a regular language?
-
-\item What is the language recognised by the regular expressions $(\varnothing^*)^*$.
\item If a regular expression $r$ does not contain any occurrence of $\varnothing$,
is it possible for $L(r)$ to be empty?
\item Define the tokens and regular expressions for a language
- consisting of numbers, left-parenthesis $($,
- right-parenthesis $)$, identifiers and the operations $+$,
- $-$ and $*$. Can the following strings in this language
- be lexed?
+ consisting of numbers, left-parenthesis $($, right-parenthesis $)$,
+ identifiers and the operations $+$, $-$ and $*$. Can the following
+ strings in this language be lexed?
-\begin{itemize}
+ \begin{itemize}
\item $(a + 3) * b$
\item $)()++ -33$
\item $(a / 3) * 3$
-\end{itemize}
+ \end{itemize}
-In case they can, can you give the corresponding token
-sequences.
+ In case they can, can you give the corresponding token
+ sequences.
\item Assume that $s^{-1}$ stands for the operation of reversing a
-string $s$. Given the following \emph{reversing} function on regular
-expressions
+ string $s$. Given the following \emph{reversing} function on regular
+ expressions
-\begin{center}
-\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
-$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
-$rev(c)$ & $\dn$ & $c$\\
-$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
-$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
-$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
-\end{tabular}
-\end{center}
+ \begin{center}
+ \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
+ $rev(\varnothing)$ & $\dn$ & $\varnothing$\\
+ $rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+ $rev(c)$ & $\dn$ & $c$\\
+ $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
+ $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+ $rev(r^*)$ & $\dn$ & $rev(r)^*$\\
+ \end{tabular}
+ \end{center}
-
-and the set
+ and the set
-\begin{center}
-$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
-\end{center}
+ \begin{center}
+ $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
+ \end{center}
-prove whether
+ prove whether
-\begin{center}
-$L(rev(r)) = Rev (L(r))$
-\end{center}
+ \begin{center}
+ $L(rev(r)) = Rev (L(r))$
+ \end{center}
-holds.
-
-\item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings
-that do not contain any substring $bb$ and end in $a$.
+ holds.
-\item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}.
-Give a regular expression that can recognise comments
-of the form
+\item Assume the delimiters for comments are \texttt{$\slash$*} and
+ \texttt{*$\slash$}. Give a regular expression that can recognise
+ comments of the form
-\begin{center}
-\texttt{$\slash$*~\ldots{}~*$\slash$}
-\end{center}
+ \begin{center}
+ \texttt{$\slash$*~\ldots{}~*$\slash$}
+ \end{center}
-where the three dots stand for arbitrary characters, but not comment delimiters.
-(Hint: You can assume you are already given a regular expression written \texttt{ALL},
-that can recognise any character, and a regular expression \texttt{NOT} that recognises
-the complement of a regular expression.)
+ where the three dots stand for arbitrary characters, but not comment delimiters.
+ (Hint: You can assume you are already given a regular expression written \texttt{ALL},
+ that can recognise any character, and a regular expression \texttt{NOT} that recognises
+ the complement of a regular expression.)
@@ -92,14 +81,6 @@
%match the regular expression.
\end{enumerate}
-% explain what is a context-free grammar and the language it generates
-%
-%
-%
-%
-%
-% does (a + b)*b+ and (a*b+) + (b*b+) define the same language
-
\end{document}
--- a/hws/hw05.tex Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw05.tex Fri Oct 10 16:59:22 2014 +0100
@@ -10,6 +10,10 @@
\begin{document}
+% explain what is a context-free grammar and the language it generates
+%
+
+
\section*{Homework 5}
\begin{enumerate}
@@ -31,80 +35,7 @@
$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^*$.)\
\item Recall the definitions for $Der$ and $der$ from the lectures.
Prove by induction on $r$ the property that