You have the following two tokens $($t$1$ and t$2)$ and their corresponding regular expressions.

Token : regular expression

t$1$ : $($a b $0)$

t$2$ : a $($b $|0)*($a $|0)*$

In the above, $($a$,$ b$,0)$ is the set of alphabets, represents Kleene closure, and t$1$ has higher precedence than t$2.$

Problem $1(30$ points$)$

Convert two regular expressions for t$1$ and t$2$ into twin NFAs through the following two steps:

$1.$ Build their own parse trees, and

$2.$ Convert the parse trees into NFA using the McNaughton$-$Yamada$-$Thompson algorithm.

The NFA you construct must be precisely produced by the McNaughton$-$Yamada$-$Thompson algorithm $-$ you should not omit any states or e$-$transitions no matter how unnecessary they may seem $($especially for Kleene closure and union$).$

Problem $2(30$ points$)$

Add a new state, and merge the two NFAs to share the same "start" state, like the right figure that merges two regular expressions a and abb. Then, convert your NEA to DFA using the algorithm discussed in class. Draw your transition table or DFA diagram, and show your work to get full points

In your transition table, if you cannot define a transition state since it becomes an empty set $($a dead state$),$ mark in as $"."$ In your DFA diagram, you do not need to draw dead states.

After determining DFA, mark the final states using double circles, and identify their accepting tokens.

Problem $3(30$ points$)$

Minimize your DFA by performing the following steps:

$1)$ Add a dead state into your DFA $($you can omit this step of adding the dead state$)$;

$2)$ Minimize its states using the Moore's algorithm discussed in class;

$3)$ Delete the dead state from your minimized DEA;

$4)$ Draw its final minimized diagram.

You can minimize DFA using Moore's algorithm without explicitly introducing dead states $($in step $1).$

After determining minimized DFA, mark the final states using double circles, and identify their corresponding accepting tokens.

Note that the final states also can be split based on the accepting tokens.