Datasets for String Classification
Your description corresponds to the general problem of grammatical inference (or grammar induction): as opposed to statistical models, the goal is to learn the exact language represented as a formal grammar. Importantly this is symbolic learning, i.e. there is no concept of minimizing error because errors are not acceptable at all.
As far as I know the field is rather theoretical, as opposed to statistical ML: one formally proves that some classes of languages can or cannot be learnt under specific constraints. A type of learning framework which used to be studied in this context (not sure if it's still active) is language identification in the limit. A quite different framework is Probably approximately correct learning (PAC), but in this is more general and not strictly about grammatical inference (to the best of my knowledge).
So I'm not aware of any real dataset: in general arbitrary datasets don't have the kind of formal constraints which are relevant for this kind of problem. But it's possible that some parts of the literature contain at least artificial datasets.