Let Σ3 = {[0; 0; 0], ... [1; 1; 1]}
B = { w ∈ Σ3* | the bottom row is the sum of the top two rows}
Since addition is carried out from right to left, we can make a machine for the reverse of this language. If we add 2 bits in one column with a possible carry from a previous column, the sum can be at most 1+1+1 = 11. Therefore the carry can either be 0 or 1 and that is what we have to remember at any stage. Therefore there can be 2 states: 'carry 0' and 'carry 1' (here you add a carry of 1 to the top 2 bits).
For example if you are in the 'carry 1' state and you see a [0; 0; 0] you go to the dead state (because 0+0+1 = 1 and the bottom bit is a 0). But if you see a [0; 1; 0], 0+1+1 = 10 and you loop back to the 'carry 1' state. Since there shouldn't be any carry out of the left-most column, 'carry 0' is the accept state.
B = { w ∈ Σ3* | the bottom row is the sum of the top two rows}
Since addition is carried out from right to left, we can make a machine for the reverse of this language. If we add 2 bits in one column with a possible carry from a previous column, the sum can be at most 1+1+1 = 11. Therefore the carry can either be 0 or 1 and that is what we have to remember at any stage. Therefore there can be 2 states: 'carry 0' and 'carry 1' (here you add a carry of 1 to the top 2 bits).
For example if you are in the 'carry 1' state and you see a [0; 0; 0] you go to the dead state (because 0+0+1 = 1 and the bottom bit is a 0). But if you see a [0; 1; 0], 0+1+1 = 10 and you loop back to the 'carry 1' state. Since there shouldn't be any carry out of the left-most column, 'carry 0' is the accept state.
No comments:
Post a Comment