# HG changeset patch # User Christian Urban # Date 1412956762 -3600 # Node ID a1544b804d1e5a110eb1b4143d7e621543f86a6b # Parent ae039d6ae3f292dfb2415dd8fa2a121015eca041 updated homeworks diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw01.tex --- 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} diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw02.tex --- 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} diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw03.tex --- 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: diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw04.tex --- 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} diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw05.tex --- 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