## Week 9 Assignment 9 (15,16 April) Automata

1. Create NFA automata using Thompson and Glushkov constructions:

(aba|ab)*(bab|a)*b

2. Make a DFA out of the two above automata

3. Minimize the two above automata. And extract the equivalent RE from that automaton.

4. Make an automaton recognizing the above regular expression allowing one edit mistake (insertion, deletion, substitution).

5. Provide an algorithm for minimizing automata by merging equivalent states of the automatons. Use as an example the sequences marked with + (positive) from Bonus task. Hint: draw first a trie (prefix tree) of the examples.

6. **Bonus (3p)** Create a small automaton that recognizes all positive examples and none of the negative examples from below. Note that the automaton should generalise from the examples. Which other sequences would belong to the language of that automaton? Which strategy did you use? Give it your best shot and try to discuss ideas that came to mind first, second, ....

AGAGGAT + ATGAG + AGAT + AAAGAG + GAT + GAGGAGAT + A + ATGAT – AA – AAATGA – AAGAT -