PLEASE ANSWER ONLY IF YOU KNOW

SUBJECT IS THEORETICAL COMPUTER SCIENCE

Deterministic finite automata (DFA)

PLEASE SHOW WORK

PLEASE SHOW WORK

A bit is a binary digit, which can be either 1 or 0 . When two bits are added including a carry bit, the resultant bit will be 1 if the sum of the bits and the carry bit is odd; otherwise, it will be 0 . Furthermore, the resulting carry bit of the same operation will be 1 if the sum of the bits and the carry bit is greater than 1 ; otherwise, it will be 0 . Since a computer has limited storage for data, it is possible for an overflow flag to be thrown, which occurs when the final carry bit is 1 . Thus, given two binary numbers [sequences of bits] with the initial carry bit equal to 0 , construct a DFA that accepts if the final resultant bit of their sum is 1 and there is no overflow. Let ={(0,0),(0,1),(1,0),(1,1)}, which represent all possible inputs. For instance, the sum of the numbers 1101 and 0111 will generate the input string w=(1,1)(0,1)(1,1)(1,0)[ bits in reverse] and it will be rejected