-1

Can someone please points out why it is true. it is from "Introduction to the theory of computation_third edition - Michael Sipser" Page 65. Assume that Alphabet E is {0,1}. Thank you.

enter image description here

Dmomo
  • 143
  • I am not familiar with what $\Sigma^*$ means, but look - $0\langle\text{anything}\rangle 0$ starts and ends with $0$; $1\langle\text{anything}\rangle 1$ starts and ends with $1$; $0$ itself starts and ends with $0$; and $1$ itself starts and ends with $1$. Does that help? –  Jan 11 '18 at 23:39
  • Could you give details on what you do not understand? – J.-E. Pin Jan 13 '18 at 11:25
  • So, we use w where w starts and ends with the same symbol to represent the Left hand side which is 0 concatenates with the power set of ∑ and concatenates with 0 union with (1 concatenates power set of ∑ and concatenates with 1) union with 0 and union with 1. I can't visualize how they are equal, I most likely reading the left hand side wrong then. can you explain the left hand side better ? @J.-E.Pin thank you in advance. – Dmomo Jan 13 '18 at 17:50

1 Answers1

1

In more details, the left hand side is the union of the four sets $E_0, E_1, F_0$ and $F_1$ where $$ E_0 = \{0u0 \mid u \in \Sigma^*\},\ E_1 = \{1u1 \mid u \in \Sigma^*\}, F_0 = \{0\}\ \text{and}\ F_1 = \{1\} $$ You can verify that if you take a word in one of these four sets, then its first letter will be equal to its last letter. For instance, if $v \in E_0$, then $v = 0u0$ for some word $u$, and the first and the last letter of $v$ are both equal to $0$. If $v \in F_0$, then $v = 0$ and again the first and the last letter of $v$ are both eqaul to $0$.

Conversely, if the first and the last letter of a word are equal, then this word belongs to one of these four sets. Do you see why now?

J.-E. Pin
  • 40,163