Re: DFA recognizing the language {w | top(w) mod 3 = bottom(w) mod 3}

"Barb Knox" <see@xxxxxxxxx> wrote in message news:see-36211D.16542923012007@xxxxxxxxxxxxxxxxxx
In article <12ratat6dstkc03@xxxxxxxxxxxxxxxxxx>,
"meyousikmann" <meyousikmann@xxxxxxxxx> wrote:

I am stumped on constructing this DFA. Can anyone offer any pointers?

For the alphabet:

| 0 | | 0 | | 1 | | 1 |
| 0 | | 1 | | 0 | | 1 |

where the strings over this alphabet represent a "top row" and a "bottom
row" and each row represents a number in binary starting with the least
significant bit.

Design a DFA to recognize the language {w | top(w) mod 3 = bottom(w) mod 3}.

This can be solved with 18 = 3 x 3 x 2 states or 6 = 3 x 2 states but I
can't seem to figure it out.

Any help?

Hint:

In base ten the remainder of a number mod 11 is ((sum of even-power
digits) - (sum of odd-power digits)) mod 11. E.g 123 mod 11 = ((1+3) -
(2)) mod 11 = 2 mod 11 = 2.

Similarly, in base 2 the remainder of a number mod 11_2 is ((sum of
even-power digits) - (sum of odd-power digits)) mod 11_2.

So, 0/0 and 1/1 don't affect the mod-3 difference of top - bottom in any
bit position, 1/0 adds 1 to the difference (mod 3) if it's in an even
bit position and subtracts 1 in an odd bit position, and 0/1 does the
reverse.

So at minimum you need to simultaneously keep track of whether it's
currently an even or odd bit position (2 possibilities), and the current
mod-3 difference (3 possibilities), which requires 2*3 states.

(And I expect that the alluded-to 2*3*3-state solution keeps track of
the top mod 3 and bottom mod 3 separately, with the accepting states
being those where the two are equal.)

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------

Thank you so much for the pointers. It is going to take me a few reads to understand this.

.

Relevant Pages

  • Re: DFA recognizing the language {w | top(w) mod 3 = bottom(w) mod 3}
    ... where the strings over this alphabet represent a "top row" and a "bottom ... currently an even or odd bit position, ... the top mod 3 and bottom mod 3 separately, with the accepting states ...
    (comp.theory)
  • Re: Save the battleships - USS Iowa and USS Wisconsin
    ... > So after another long BB thread, we finally get to the bottom of it. ... not too odd as it is only one step removed from the conspiro wackos ... that a Chief Machinist had a GQ station in a mount. ... This is just another skill that needs to be learned. ...
    (sci.military.naval)
  • Re: Halves vs Halves Not
    ... their car number first, so they have the lower numbered cars, ... I expected u to offer THE answer as to why the top half of the alphabet ... get more T10s than the bottom half. ...
    (rec.autos.sport.nascar)
  • Re: Halves vs Halves Not
    ... their car number first, so they have the lower numbered cars, ... I expected u to offer THE answer as to why the top half of the alphabet ... get more T10s than the bottom half. ...
    (rec.autos.sport.nascar)
  • Re: vertical alignment problem
    ... copying and include the paragraph mark when pasting, ... pages on the sheet, as one would see in a book. ... But the bottom lines are ... There is more space at the bottoms of the odd pages than ...
    (microsoft.public.word.docmanagement)