HW 07 13.11 Regular languages II
1. Take the Thompson construction of an NFA automaton from the regular expression (aa|b)*b(ab|bb)* and make it deterministic using the NFA->DFA construction
2. Take the acquired DFA and minimize it using the provided construction
3. Make the DFA using directly the construction by McNaughton and Yamada
4. Look at the slide "Learning languages". Make a smallest automaton recognising 3 positive examples (and possibly more), but not recognising any of the three negative examples.
5. What if you added some example that required recognition but which was not? Would you need to increase the automaton on each step? Try to find some examples that would demonstrate the complex nature of such minimisation task.
6. Bonus (2p) If constructing a smallest automaton consistent with examples is NP-complete, which mapping was used to prove it? (which NP problem was mapped into this task?)