diff -r b153de5339bc -r 8be0c3c09aca hws/hw03.tex --- 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}