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

"meyousikmann" <meyousikmann@xxxxxxxxx> writes:

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?

Actually, you need only three states (unless the empty string is not
accepted, in which case you need four).

What you need to keep track of is (top(w) - bottom(w)) mod 3. This is
0 exactly when top(w) mod 3 = bottom(w) mod 3. Furthermore, given
(top(w) - bottom(w)) mod 3 for a prefix of the string and a symbol c
in the alphabet you can find (top(wc) - bottom(wc)) mod 3, so you can
maintain the information. It should be an easy matter to construct
the DFA given this information.

If you still need help, consider the following:

(a+b) mod 3 = (a mod 3 + b mod 3) mod 3
(a-b) mod 3 = (a mod 3 - b mod 3) mod 3
(-1) mod 3 = 2
(-2) mod 3 = 1

Torben
.

Relevant Pages

  • Re: Getting a random letter.
    ... private string DoLameEncryption ... Dim RandomClass As New Random ... start with a random letter of the alphabet, ... having to loop through it all? ...
    (microsoft.public.dotnet.framework.aspnet)
  • RE: ascii output encryption needed as well
    ... ascii output encryption needed as well ... > those values are representable in a string, some are control values, ... (including from one arbitrary alphabet to itself). ... A typical bytewise stream cipher enciphers to and from the alphabet ...
    (SecProg)
  • Re: DFA recognizing the language {w | top(w) mod 3 = bottom(w) mod 3}
    ... For the alphabet: ... you need only three states (unless the empty string is not ... the DFA given this information. ... transition from s to t on symbol c, there is also a transition from t ...
    (comp.theory)
  • Re: How to list drives on a users computer?
    ... to get a string that starts with the drive designation. ... likely on Windoze and you can check through the alphabet. ... it might be Mac OS9 or whatever ...
    (comp.lang.java.programmer)
  • Re: infinity
    ... >>> of unique srings in the language. ... Let's have the alphabet consist of the ... If, by "potentially infinite" TO means inclusive of infinite values, ... > string length, there is a finite maximum language size. ...
    (sci.math)