hws/hw03.tex
changeset 770 c563cf946497
parent 652 4642e2073808
child 778 3e5f5d19f514
--- a/hws/hw03.tex	Sat Oct 03 00:51:47 2020 +0100
+++ b/hws/hw03.tex	Sat Oct 03 15:21:06 2020 +0100
@@ -173,10 +173,21 @@
   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?
+  $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}