Let Σ2 = {[0; 0], [0; 1], [1; 0], [1; 1]}
C = { w ∈ Σ2* | the bottom row of w is 3 times the top row }
If you multiply a number by 3, you add the number to itself left-shifted by 1 bit. For example
Using the above idea, we can make a machine for the reverse of the language. There are now 2 things to remember: the previous symbol and any carry from the previous column. There are 4 states:
previous symbol carry
s00 0 0
s01 0 1
s10 1 0
s11 1 1
C = { w ∈ Σ2* | the bottom row of w is 3 times the top row }
If you multiply a number by 3, you add the number to itself left-shifted by 1 bit. For example
1011
* 11
----
1011
10110
-----
100001
Using the above idea, we can make a machine for the reverse of the language. There are now 2 things to remember: the previous symbol and any carry from the previous column. There are 4 states:
previous symbol carry
s00 0 0
s01 0 1
s10 1 0
s11 1 1
Why is s01 not an accept state? Just realized that.
ReplyDeleteThere should be no carry out of the last bit. Now s00 and s01 are the only states in contention.
The bottom number should be 3 times the top number and its length should not be more than that of the top number (leading zeros and all). Now if a string starts with [1;x] the top number multiplied by 3 is bound to occupy more bits than itself. It can never be a member of C. That is the reason if a string belongs to the reverse of C, the last bit at the top can never be 1. So the 'previous symbol' at the end of a string must be 0. Therefore s00 and not s01.
...afafafffafa