Prove the following language is regular by using the Myhill-Nerode Relation

129 Views Asked by At

$w=\{w | \text{w begins with a 1 and ends with a 0}\}$

Let $A_1\{w|\text{w begins with a 1 and ends with a 0}\}$
$A_2=\{w|\text{w begins with a 0 and ends with a 0}\}$
$A_3=\{w|\text{w begins with a 0 and ends with a 1}\}$
$A_4=\{w|\text{w begins with a 1 and ends with a 0}\}$

1) Any $x,y\in A_1$ are related by $R_{A_1}$ because let's take any string z that ends with a 0. If we take any $x,y\in A_1$ then $xz \in A_1$ and $yz \in A_1$

2) Any x,y in $A_2$ are related by $R_L$ because if we take any $z\in \sum^*$, $xz \notin A_1$ and $yz \notin A_1$ since every string in $A_2$ starts with a 0.

3) $A_3$ same reason as 2)

4) $A_4$ Same reason as 1

And we know that $A_1 \cup A_2 \cup A_3 \cup A_4 = \sum^*$. Therefore, $A_1$ is regular

How does that look?