1
$\begingroup$

Let $\Sigma_{2}={ \begin{bmatrix} 0\\ 0 \end{bmatrix}, \begin{bmatrix} 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 1 \end{bmatrix}}$

Here $\Sigma_{2}$ contains all columns of $0$ and $1$s of height $2$. A string of symbols in $\Sigma_{2}$ gives two rows of 0s and 1s. Consider each row to be a binary number and let:

$$C=\{w\in \Sigma^*_2 \mid\text{ the bottom row of }w\text{ is }3\text{ times the top row}\}\;.$$

For example: ${ \begin{bmatrix} 0\\ 0 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix}\begin{bmatrix} 1\\ 1 \end{bmatrix}\begin{bmatrix} 0\\ 0 \end{bmatrix}\in C}$ but ${ \begin{bmatrix} 0\\ 1 \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix}\begin{bmatrix} 1\\ 0 \end{bmatrix}\notin C}$

Show that $C$ is regular.

I would like to get some tips on how to approach this problem, as I am new to learning about formal language theory.

$\endgroup$

2 Answers 2

4
$\begingroup$

It’s easiest, I think, to use the fact that a language is regular if and only if its reversal is regular. (This pretty easy to prove using either regular grammars or DFAs, if you’ve not already seen it.) I’d construct a DFA that recognizes $C^R$, the reversal of $C$. In effect this amounts to thinking about a DFA that scans words backwards. I claim that if you scan a word $s\in\Sigma_2^*$ from right to left, it’s easy to tell whether it’s in $C$.

In order to be in $C$, $w$ can terminate in any number of $0\brack 0$s. Now $3\cdot1=3=11_{\text{two}}$, so when you finally encounter a $1$ in the top line, you must have a $1$ below it, and the multiplication also has a carry to the next column over. Thus, you need a $1\brack 1$, and you know that the multiplication of the top line by $3$ has a carry into the next column over. Continue in this fashion: as each symbol comes in, you need only its top symbol and the knowledge of whether there was a carry from the next column over in order to tell whether its bottom symbol is the right one. Use the states of the DFA to keep track of whether you have an incoming carry.

$\endgroup$
2
$\begingroup$

Hint 1: If $\mathcal L$ is a regular language, then $\mathcal L^R = \{ w^R : w\in \mathcal L \}$ is also regular. ($w^R$ is the reverse of the string $w$.)

Hint 2:

The machine can go right to left on the input, checking that the multiplication is done correctly, storing only the carry bit from the previous input.

$\endgroup$
6
  • $\begingroup$ @Matt: You might want to wait a while before accepting this answer, to see if you get one you like better. $\endgroup$
    – MJD
    Feb 13, 2013 at 4:03
  • $\begingroup$ How do you prove the Hint 1? Thank you. $\endgroup$
    – manooooh
    Jan 5, 2020 at 4:54
  • $\begingroup$ Reverse the regular expression. $\endgroup$
    – MJD
    Jan 5, 2020 at 5:02
  • $\begingroup$ I do not know what you mean. Are you proposing a "visual" proof? $\endgroup$
    – manooooh
    Jan 5, 2020 at 5:02
  • $\begingroup$ A regular language $\mathcal L$ can be represented by a regular expression $x_{\mathcal L}$. Given $x_{\mathcal L}$ it's not hard to construct the related regular expression for $\mathcal L^R$. This proves that $\mathcal L^R$ is also regular. $\endgroup$
    – MJD
    Jan 5, 2020 at 18:44

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .