Exercise $24$ Language of a state

$(6$ points$)$

You already know that the language of a deterministic finite automaton $($DFA$)$ is the set of all words

$w$ such that beginning at the start state and reading the word $w,$ the DFA ends up in a final state.

We now define the language of a state $Z(s_i)$ as the set of words $w$ such that beginning at a given state

$s_i$ and reading the word $w,$ the DFA ends up in a final state. Formally: ${?}^2$

$Z(s_i)=\{win{}^{**}|(hat())(s_i,w)inE\}$

Now let the following deterministic automaton $M$ be given:

As an example, starting at $s_2,$ a final state can be reached by reading $b$ or bab, therefore binZ$(s_2)$ and

babinZ$(s_2).$ On the other hand, $ba!$inZ$(s_2),$ baa $Z(s_2),!$inZ$(s_2),$ since reading all these words

results in a non$-$final state being reached.

$($a$)$ For each state of $M,$ specify the language of this state. You can use set notation $(Z(s_i)=\{dots\})$

or regular expressions $(Z(s_i)=L(dots)).$

$($b$)$ Recall the definition of Myhill$-$Nerode equivalence:

$x-={?}_L$yLongleftrightarrow for all zin${}^{**}it$ holds that $(xzinL>$yzinL$)$

We have hat$()(s_1,a)=s_2$ and hat$()(s_1,$aba$)=s_4.$ Also, it is easy to see that $Z(s_2)=Z(s_4)($if you did

not solve subtask $($a$),$ then you may simply assume that this is true$).$ Based on this, what is the

relationship between the words a and aba regarding Myhill$-$Nerode equivalence? Give a short

justification for your answer.

$($c$)$ Specify the Myhill$-$Nerode equivalence class of the word aba $([aba{]}_{{}_{T(M)}}=\{dots\}).$