Q $5.(6$ points $+4$ extra credit$)$ Two DFAs $($or NFAs$)$ are isomorphic if they are the same, up

to re$-$labeling the states. We saw in class how to build a minimal DFA recognizing any language;

by inspecting that proof, one can see that the minimal DFA is unique up to isomorphism. In this

problem we will see that this is not true of NFAs.

$($a$)$ Let $=\{a,b,c\}.$ Give two non$-$isomorphic $5-$state NFAs $($with no epsilon$-$moves$)$ recognizing

the language $L=\{xyin{}^2$:$xy\}=\{ab,ac,bc,ba,ca,cb\}$ over the alphabet $.$

$($b$)$ Extra credit: Show that there is no NFA recognizing $L$ with fewer than $5$ states. Hint:

Show that $(q_0,x)(q_0,y)$ for any two symbols $xy.$

Conclude that the minimal NFA is not unique.