\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 bein 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 nodescan 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}\itemGiven 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 asthis automaton. (Hint: If you use Brzozwski's method, you can assumeArden'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 \[L(der\,c\,r) = Der\,c\,(L(r))\]holds.\end{enumerate}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: