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

meyousikmann 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?

Are you aware of the concept of "casting out nines" in decimal arithmetic?

Patricia
.

Relevant Pages

  • Re: DFA recognizing the language {w | top(w) mod 3 = bottom(w) mod 3}
    ... For the alphabet: ... 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 DFA given this information. ...
    (comp.theory)
  • 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)