(DFA Construction: Addition Verification) Let sigma_2 = (0, 1), and define sigma

Question

(DFA Construction: Addition Verification) Let sigma_2 = (0, 1), and define sigma - sigma^3_2, Informally, sigma is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s elementof sigma*: it is a sequence of such triples. We want to "verify" binary addition of numbers in the first two coordinates by checking that it is equal to the third. Let A be the language of such triples such that the concatenation of the first coordinates, as a number, and the concatenation of the second coordinates, as a number, sum to be equal to the third. For example, if w = (0, 1, 1)(1, 1, 1)(0, 0, 1)(1, 0, 1), this is encoding 0101_2 + 1100_2 = 1111_2, which is false: therefore, w NotElement A. Prove that A is regular.

Explanation / Answer

Step 1) Reverse the strings

Step 2) The first number’s viz. a binary representation is in the top row, the second number’s viz b representation is in the middle row, and the result is in the bottom row viz. c. Let L be the language of strings over this alphabet which represent correct addition statements as described above. As an example, correctly representing 4 + 2 = 6 in this scheme would give the following string (first input symbol on the left)

0 0 1

0 1 0

0 1 1

Step 3) Equations are

Ci = Ai + Bi + ciin

cini+1 = (Ai & Bi) | (Ai | Bi) & ciin = ciout

DFA of 5 states will be required.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.