# Proving a language (ir)regular (standard methods have failed)

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.

• 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.
– Dib
Apr 19 '14 at 15:46
• @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. Apr 19 '14 at 21:26
• 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. Apr 19 '14 at 22:59