\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^*$.)\+
−
+
−
\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: +
−