\documentclass{article}+
−
\usepackage{../style}+
−
\usepackage{../graphics}+
−
+
−
\begin{document}+
−
+
−
\section*{Homework 3}+
−
+
−
\HEADER+
−
+
−
\begin{enumerate}+
−
\item The regular expression matchers in Java, Python and Ruby can be+
−
  very slow with some (basic) regular expressions. What is the main+
−
  reason for this inefficient computation?+
−
  +
−
\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+
−
      +
−
  \begin{center} $r ::=+
−
    \ZERO \;|\; \ONE \;|\; 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) = \{\}$+
−
%  \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+
−
+
−
  \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}+
−
+
−
  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 automaton $A(\varSigma, 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 following deterministic finite automaton 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}[>=stealth',very thick,auto,+
−
                        every state/.style={minimum size=0pt,+
−
                        inner sep=2pt,draw=blue!50,very thick,+
−
                        fill=blue!20},scale=2]+
−
      \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}[>=stealth',very thick,auto,+
−
                        every state/.style={minimum size=0pt,+
−
                        inner sep=2pt,draw=blue!50,very thick,+
−
                        fill=blue!20},scale=2]+
−
      \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 \textbf{(Deleted for 2017, 2018, 2019)}+
−
  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.+
−
+
−
  \begin{center}+
−
    \begin{tikzpicture}[>=stealth',very thick,auto,+
−
                        every state/.style={minimum size=0pt,+
−
                        inner sep=2pt,draw=blue!50,very thick,+
−
                        fill=blue!20},scale=2]+
−
      \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 finite deterministic automaton over the alphabet $\{a, b\}$:+
−
+
−
  \begin{center}+
−
    \begin{tikzpicture}[scale=2,>=stealth',very thick,auto,+
−
                        every state/.style={minimum size=0pt,+
−
                        inner sep=2pt,draw=blue!50,very thick,+
−
                        fill=blue!20}]+
−
      \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 If a non-deterministic finite automaton (NFA) has+
−
  $n$ states. How many states does a deterministic +
−
  automaton (DFA) that can recognise the same language+
−
  as the NFA maximal need?+
−
+
−
\item Prove that for all regular expressions $r$ we have+
−
      +
−
\begin{center} +
−
  $\textit{nullable}(r) \quad \text{if and only if} +
−
  \quad [] \in L(r)$ +
−
\end{center}+
−
+
−
      Write down clearly in each case what you need to prove+
−
      and what are the assumptions. +
−
+
−
  +
−
\item \POSTSCRIPT  +
−
\end{enumerate}+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−