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

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.

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

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.

Patricia
.

Relevant Pages

  • Re: String Sort???
    ... Since the elements of the array are Strings, ... In reality the correct way to sort strings is dependent on Locale. ... And to your credit lexicographic is sometimes called alphabetic, but the use of the term alphabet there is the mathematical meaning of alphabet not the natural meaning that most people would use. ...
    (comp.lang.java.programmer)
  • Re: powerset with cardinality of 3^n
    ... >> from some alphabet of symbols. ... >> to strings of digits, i.e., decimal integers. ... exercise in powersets and cardinalities. ... probably be larger than the regular powerset. ...
    (sci.math)
  • Re: wffs definition
    ... wffs of a language L are defined as a subset of the set of strings over the alphabet of L (i.e. finite sequences of symbols of L) as ...
    (sci.math)
  • Context-free grammar
    ... But I have trouble believing it is wrong. ... I used the first solution ... The set of strings over the alphabet with more a's than b's. ...
    (comp.theory)
  • Re: infinity
    ... >>>Given any string length and alphabet, that is the maximum number of unique ... >> strings, then there is a finite string that is not in U. ... Didn't you claim that the set of all finite naturals is a finite set? ... The sum over all finite values of L of S^L is infinite. ...
    (sci.math)