Problema desafiante sobre NFA y DFA. Mostrando que un lenguaje es regular

Question

Deje que $\sum_3$ contenga todas las columnas de tamaño 3 de 0s y 1s de la siguiente manera $$\sum_{3}= \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}$$

Una cadena en 3 da tres filas de 0s y 1s. Considere cada fila como un número binario. Deje que

$B = \{ _^3|$ la fila de abajo de es la suma de las dos filas de arriba}

Por ejemplo,

$\begin{bmatrix}0 \\ 0 \\ 1\end{bmatrix}\begin{bmatrix}1 \\ 0 \\ 0 \end{bmatrix}\begin{bmatrix}1 \\ 1 \\ 0 \end{bmatrix}\in B$, pero $\begin{bmatrix}0 \\ 0 \\ 1 \end{bmatrix}\begin{bmatrix}1 \\ 0 \\ 1\end{bmatrix}\notin B$

Demuestre que B es regular

Este problema está marcado como desafiante en el libro. Sugiere que trabaje en $B^R$ primero y luego muestre que B es regular. Se me permite usar el siguiente teorema

Teorema: Si $B$ es regular entonces $B^R$ es regular

$B^R$ es simplemente todas las cadenas invertidas en B

¿Cómo abordaría este problema?. No sé por qué $B^R$ ayudaría porque dado el lenguaje, parece que no hay $B^R$ o $B^R=B$

Answer 1

Piensa en tu lenguaje $B$ como el lenguaje de todas las sumas largas binarias válidas. Ahora necesitas definir un AFN que verifique si una suma larga es correcta. Al realizar una suma larga desde el bit menos significativo primero, esto es más fácil de hacer para $B^R$.

Necesitarás llevar un seguimiento de un bit de acarreo usando dos estados diferentes, comenzando en el estado sin acarreo. Luego, estando en uno de esos dos estados, algunas entradas son válidas, algunas son inválidas y algunas cambian el acarreo. Por ejemplo, $\begin{bmatrix}0\ 0\ 1\end{bmatrix}^T$ es válida en el estado de acarreo y no produce un acarreo, mientras que es inválida en el estado sin acarreo; $\begin{bmatrix}1\ 1\ 0\end{bmatrix}^T$ es válida si no hay acarreo, pero produce un acarreo.

Aceptas una cadena si te quedas sin acarreo después de leerla por completo.