\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: + −