Write regular expressions which describe the following languages. Remember your answers must only use symbols from definition 3.5, i.e., letters from the alphabet (which isin each case), , , , , , and .
Try to write the regular expressions from scratch rather than converting equivalent NFAs. If you decide to do the latter, make sure your result is as simple as possible.
Convert the following regular expressions into nondeterministic finite automata using the method shown in the videos. Represent the automata in the form of diagrams. You should simplify your models as you build them – for example you may remove redundant states and combine states that are linked with epsilon transitions, but make sure the language is unchanged.
Convert these nondeterministic finite automata (repeated from Problem Sheet 1) into regular expressions using the method shown in the lessons. Show your working.
Note: the order in which you remove states in the conversion process will greatly affect the complexity of the resulting regular expression. Try to choose this order in a way that creates the simplest result. You might want to try multiple options before deciding which one to use for your submission.