(Conversions: Part 1): Instead of talking about a specific regex, let's consider the language of regular expressions (as strings) over the alphabet {0, 1, ,[.],0,U,o, 1 ( represents the empty string as a character, o represents concatenation as a character, U represents union as a character, * represents Kleene star as a character, and represent parentheses/brackets as characters) Note: , [. J' ( ,U, o, * are actual characters in this setting. We will limit our attention to such regexes that do not have sub-brackets. For example, [0 U 11*0 1 o 0] U 0 o 1** is such an expression, and [O 01 U 11 is not. For example, the regex R for "single characters" is: because brackets need to be matched up. Similar reasoning goes for U, o, x. Create a regex S that recognizes exactly the language of such regexes.3 Explain, in English, why your regex is correct (Hint: define "simpler" regexes first, and use them as "black boxes" for the final regex. The regex R above can be of good use.) For partial credit, you can instead handle the case of no brackets at all as is described in Part 3 below. (If you do so for Part 1, you won't lose any points in Part 2 if applied correctly.) (Conversions: Part 2) Convert S, from Part 1, into an equivalent NFA N, using exactly the procedure described in class. Also, in English, briefly describe how your NFA was produced (Hint: the NFA is somewhat large so a transition table is recommended instead of a state diagram, or you can make "simpler" NFAs and use them as black boxes like before