CMI2012-B-02a

Question

For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be $\Sigma_{0 \leq i < n} 2^{n-1-i}.a_i$
Let $\Sigma = \{(0, 0),(0, 1),(1, 0),(1, 1)\}$.

1. Construct a finite automaton that accepts the set of all strings $(a_0, b_0)(a_1, b_1) \dots (a_{n−1}, b_{n−1}) \in \: \Sigma^*$ such that $val(b_0b_1 \dots b_{n−1}) = 2 · val(a_0a_1 \dots a_{n−1})$.

Comments

In your DFA diagram, q0 & q1 are equivalent, thus we need 3 states to build this:

 

---

@rfzahid

if language contain ∈, then you are absolutely right !

But i have doubt that " is language contain ∈ ? " --- i am not able to decide !

Answer 1

Given that for a binary string    $x=a_0a_1a_2\dots a_{n-1}$

                 $val(x)=\sum_{i=0}^{n-1}2^{n-1-i}. \ a_i$

Here, $val(x)$ is the decimal equivalent of the binary number $x$.

For example,

                $x=1010$

               $val(x)=2^3.1+2^2.0+2^1.1+2^0.0$
                             $= 8+2=10$

They specified that     $\sum= \{(0,0)(0,1)(1,0)(1,1)\}$

That is every pair in the input $(a_0,b_0) (a_1,b_1) \dots (a_{n-1},b_{n-1})$ will take any one of these $4$ possibilities.

Our task is to construct a Finite Automaton for the input such that 

                                 $val( b_0b_1.....b_{n-1})=2.val(a_0a_1.......a_{n-1})$

Consider an input     $a_0 \ b_0 \ \ \ a_1 \  b_1 \ \ \ a_2 \ b_2 \ \ \ a_3 \ b_3$
                                    $(0,1) \  \  (1,1) \ \ \ (1,0) \ \ \ (0,0)$

                          $val(a_0a_1a_2a_3)=val(0110)=6$

                          $val(b_0b_1b_2b_3)=val(1100)=12$
 

Here, $val(b_0b_1b_2b_3)=2.val(a_0a_1a_2a_3)$

So the input  $(0,1) (1,1) (1,0) (0,0)$ should have to be accepted by the Finite Automaton.

Idea of constructing DFA:
Note : the DFA should reject the input starting with $1$.

            Ex: $(1,1) (0,1) (1,1) (0,0)$

Reason: It is not possible for the bit sequence  $b_0b_1.....b_{n-1}$  to represent a value equal to twice the value of the sequence $a_0a_1.......a_{n-1}$  if $a_0=1$.

If $a_0=1$, then the number of bits required to represent the value equal to twice the value of $a_0a_1.......a_{n-1}$ is $n+1$.

Ex:   Let $n=4$ and $a_0a_1a_2a_3=(1000)=8$
Number of bits required to represent $16$ is $5$ but the number of bits available is $b_0b_1b_2b_3$ which is $4$.

So, the input should not start with $1$.

Consider the example,

                                    $(0,1) \  \  (1,1) \ \ \ (1,0) \ \ \ (0,0)$     
                                     $a_0 \ b_0 \ \ \ a_1 \  b_1 \ \ \ a_2 \ b_2 \ \ \ a_3 \ b_3$
 

                                    $(a_0a_1a_2a_3)=(0110)=6$

                                    $(b_0b_1b_2b_3)=(1100)=12$

Here we can clearly see that
    $b_0=a_1$
    $b_1=a_2$
    $b_2=a_3$
    $b_3=0$

This condition can be generalized as,    
    $b_0=a_1$
    $b_1=a_2$
    $b_2=a_3$
          .
          .
          .
    $b_{n-2}=a_{n-1}$
    $b_{n-1}=0$

It is our task to construct the DFA satisfying the above condition.

This is the corresponding DFA:

 

Comments

Great explaination doubling the binary sequence just means left shifting the sequence by 1 ..therefore last bit i.e.
$$b_{n-1}=0$$
will always be 0.

---

@balaeinstein

Is there any need of q5 state? Just make 0-transition of q4 to q3 and,

1-transition of q4 to q2.

---

what is the regular expression for the following FA?