This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language"?
For simplicity, consider only "legacy" P2PKH Bitcoin addresses: a valid address consists of the character "1" followed by 25 to 33 Base58 (
123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz) symbols. There is an additional constraint that the last 32 bits of the address are a checksum which equals the first 32 bits of the result of the double SHA-256 hash of the rest of the address.
Obviously, the set of Bitcoin addresses under this definition is a regular language because it is finite, although this is probably no solace to anyone who wants to write a regex to validate it! But it's more interesting to think about Bitcoin addresses of unbounded length. I believe this is not a regular language, and the pumping lemma for regular languages can be used to prove that, nor is it a context-free language, once again because of the pumping lemma (for context-free languages), although I'm not as certain because I didn't take the actual time to think of a proof of this. It's also obvious that this new language of Bitcoin addresses of up to any length is recursively-enumerable and recursive, as it's trivial to write some C code to validate strings in it and also generate strings for it.
Now, the question that I am unable to answer is this: is the set of Bitcoin addresses with up to any length a context-sensitive language?
Forgive me if this is a question with an obvious answer; I only learned this stuff last term :)