Question

Let

$\sum _3=\left\{\left[\left.\begin{array}{c}0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}\begin{array}{c}0\\ 0\\ 1\end{array}\end{array}\right],\left[\begin{array}{c}\begin{array}{c}0\\ 1\\ 0\end{array}\end{array}\right],----,\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right.\right]\right\}$

$\sum _3$contains all size 3 columns of 0s and 1 s. A string of symbols in$\sum _3$gives three rows of 0s and 1s. Consider each row to be a binary number and let B=$\left\{W\in \sum _{}*3\right\}$the bottom row of W is the sum of the top two rows}.

For example,

$\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]\in Bbut\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]\notin B$

Show that Bis regular.

(Hint: Working with $B^R$is easier. You may assume the result claimed in Problem 1.31.)

Short answer

$B^R$is the regular language, as$B^R$ is regular hence B is also regular.

Step-by-step solution

Introduction 

The given data is$\sum _3=\left\{\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right],-\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\right\}$

.A string of symbols in$\sum _3$ gives 3 rows of 0 s and 1 s-

Each row to be a binary number

B= $\left\{W\in \sum _3\right.$the bottom now of w is the same of the top two row$\left.\right\}$

Explanation 

Already know that "regular languages are closed under nerves. "

If$B^R$is regular, then automatically B is regular and vice-versa

So, first have to prove that $B^R$is regular

A language is said to be regular if some automaton recognizes it.

Let M be the automaton that recognizes$B^R$-

M has 2 states.

(i) $c_0$, which denotes that the string that we have read so for leads to a carry 0

(ii) $c_1$, that stands for carry 1 .

Now M=$\left(Q,\sum _I\delta ,q_0,F\right)$

Where Q =$\left\{c_0,c_1\right\}$= set of states

$\sum _{}=\left\{\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right],--\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\right\}=$set of alphabets

$q_0=c_0$

Start F =$c_0$= set of final states.

$\delta$is given as

$\delta \left(c_0,a\right)$=$c_0$if a =$\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]or\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]$

$-\delta \left(c_0,a\right)=c_{1_{}}$if a=$\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]$$\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]$

$-\delta \left(c_1,a\right)=c_1$if a=$\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]or\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right]$

-$\delta \left(c_1,a\right)=c_0$if a=$\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$

All other arrows go to trap state. Then, define an automation M to recognize$B^R$

Therefore $B^R$is the regular language, as$B^R$is regular hence B is also regular.