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

Patricia Shanahan <pats@xxxxxxx> writes:

Torben Ægidius Mogensen wrote:
"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.

I think I see how to do it with three states, though I have not done any
tests. However, I don't see how a three state version can find (top(wc)
- bottom(wc)) mod 3 from c and (top(w) - bottom(w)) mod 3, given that
the data starts with the least significant bit.

Starting from the most significant bit it would just be long division
with the quotient thrown away.

Ah, I didn't notice that you started with the least significant bit.

Still, it doesn't matter, as the automaton for little-endian is
exactly the same as for big-endian:

All arrows in the DFA for big-endian are bidirectional: If there is a
transition from s to t on symbol c, there is also a transition from t
to s on symbol c. Furthermore, the initial and final state are the
same, so the reverse DFA (i.e., for little-endian) is the same as the
original.

Torben

.

Relevant Pages

  • Re: DFA recognizing the language {w | top(w) mod 3 = bottom(w) mod 3}
    ... For the alphabet: ... "bottom row" and each row represents a number in binary starting with ... you need only three states (unless the empty string is not ... the DFA given this information. ...
    (comp.theory)
  • Re: Proving a regular language to be infinite
    ... I most admit that it was your example of the INFINITE algorithm that made me ... In a DFA M with n states then the longest possible path, ... is visited only once is n-1, i.e. at worst you need a string of length n-1 ... and the longest possible cycle in a graph of n vertices ...
    (comp.theory)
  • 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: 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)