III: NFA$/$GNFA$/$RE Exercise

Consider $L=\{\begin{array}{ccc}\text{a}\text{b}\text{w}\text{b}\text{a}\text{:}& \text{w}\text{i}\text{n}& {}^{**}\end{array}$ but does not contain the substring $\{$:$ba\}$ over $=\{a,b,c,d\}.$

Show that $L$ is a regular language by drawing a DFA for it$,$ with the DFA having

as few states as you can.

Draw an NFA for $L$ with as few states as you can.

Convert the NFA to a GNFA.

Convert the GNFA to an RE $($Regular Expression$)$ using the procedure discussed

in class. Show the steps. You may, but are not required to$,$ shorten intermediate

REs using identities like $R\frac{O}{?}=\frac{O}{?}$ and $R=R$ and $R\frac{O}{?}=R$ to reduce expression

swell.