As an example, starting at s$2,$ a final state can be reached by reading b or bab, therefore b in Z$($s$2)$ and

bab in Z$($s$2).$ On the other hand, ba $/$ in Z$($s$2),$ baa $/$ in Z$($s$2),\backslash$epsi $/$ in Z$($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$($si$)=\{...\})$

or regular expressions $($Z$($si$)=$ L$(...)).(3$ p$)$

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

x $$L y $$ for all z in $\backslash$Sigma

$$

it holds that $($xz in L $$ yz in L$)$

We have $\backslash$delta $($s$1,$ a$)=$ s$2$ and $\backslash$delta $($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. $(2$ p$)$

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