edited by
492 views
1 votes
1 votes
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix},…….,\begin{bmatrix} 1\\1 \\1 \end{bmatrix}\end{Bmatrix}.$

$\sum_{3}$ contains all size $3$ columns of $0’s$ and $1’s.$ A string of symbols in $\sum_{3}$ gives three rows of  $0’s$ and $1’s.$ Consider each row to be a binary number and let

$B=\{w\in\sum_{3}^{*}|\text{the bottom row of $w$ is the sum of the top two rows}\}.$

For example$,\begin{bmatrix} 0\\0 \\1 \end{bmatrix}$  $\begin{bmatrix} 1\\0 \\0 \end{bmatrix}$  $\begin{bmatrix} 1\\1 \\0 \end{bmatrix}\in B,$  but $\begin{bmatrix} 0\\0 \\1 \end{bmatrix}$ $\begin{bmatrix} 1\\0 \\1 \end{bmatrix}\notin B$

Show that $B$ is regular. $\text{(Hint$:$Working with $B^{R}$ is easier. You may assume the result claimed in question $31$})$
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
4
admin asked Apr 21, 2019
2,606 views
Convert the following regular expressions to $NFA's$ using the procedure given inTheorem $1.54.$ In all parts, $Σ = \{a, b\}.$$a(abb)^{*}\cup b$$a^{+}\cup (ab)^{+}$$(a\c...