9
$\begingroup$

I'm currently trying to prove a language regular (for personal amusement). The language is:

The language containing all numbers in ternary that have even bit-parity when encoded in binary.

Now, I've currently tried a few different approaches that have not led me to any success. I've tried using the pumping lemma (couldn't find anything to pump on), Myhill-Nerode (similar) and even counted the number of strings of each length for which the statement is true (my intuition is that it checks out with a probabilistic argument).

Are their any other approaches that might help here, or are there any intuitions that might be helpful? At this point, my best guess is that the language is not regular, but I don't seem to be able to come up with an explanation.

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you sure that it is a non-regular language ?? Consider the language on $\{0,1\}^*$ such that the strings have even number of ones. This is a regular language. Now apply homomorphism on this language to convert it into a language containing all ternary strings. The inverse homomorphism defines a encoding scheme. Regular languages are closed under homomorphism and inverse homomorphism. $\endgroup$
    – Dib
    Apr 19, 2014 at 15:46
  • $\begingroup$ @Dib I don't think that this is a valid approach, simply because I don't believe that there exists such a homomorphism. To expand, as I understand it the homomorphism must be a function from letters of the alphabet to strings, so 1, 0, 1101 must map to A, B, AABA, where A and B are strings in ternary. 1 maps to 1 in ternary, and 0 maps to 0 in ternary, but 1101 maps to 111 and not 1101 in ternary. $\endgroup$
    – James
    Apr 19, 2014 at 21:26
  • $\begingroup$ I should add that I am almost certain that this language is irregular. This is because around 50% of numbers of the type 10* (i.e. powers of 3) in base 3 have even parity, as we might reasonably expect (empirical, I have checked up to $3^{20000}$). This means that one could reasonably expect to pump on something of this form, pumping on something of the form $3^n$ to receive something like $3^{n+m}$. This would not be in the language with probability 0.5. The problem is that I cannot exactly prove this - I'd end up with a probabilistic argument. $\endgroup$
    – James
    Apr 19, 2014 at 22:59

1 Answer 1

Reset to default
10
$\begingroup$

This can be proven, but you need some nontrivial tools to do it.

Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion.

It is well-known that this set is "2-automatic"; that is, there is a finite automaton accepting exactly the base-2 expansions of elements of S. Furthermore, it is well-known that this set is not ultimately periodic (that is, it is not true that there exists a period P such that after some point C, if x >= C is in S then so is x+P). (If it were, then the associated Thue-Morse word 01101001... would be ultimately periodic, but it is known from Thue's 1912 paper not to contain any block repeated three times consecutively.)

Next, assume S is actually "3-automatic"; that is, there is an automaton accepting exactly the base-3 expansions of elements of S. Then by a classic theorem of Cobham (Math. Systems. Theory 3 (1969) 186-192, this would imply that S is ultimately periodic. But we have already seen it isn't.

You can find a lot more about these ideas in my book with Allouche, "Automatic Sequences". Warning, though, our proof of Cobham is a bit flawed, and a corrected version by Rigo can be found online here: http://arxiv.org/abs/0907.0624 .

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much. I figured I'd need some kind of nontrivial tool, but I don't have the education (yet) to work out which one! $\endgroup$
    – James
    Apr 21, 2014 at 14:48
  • $\begingroup$ @Jeffrey: Nice use of Cobham's; out of curiosity, do you believe that any proof will require it — or will embed it somehow? $\endgroup$
    – Michaël
    Apr 21, 2014 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.