Comment convertir le langage L en expression régulière

Question

https://cs.stackexchange.com/questions/82775/to-prove-or-disprove-that-language-is-regular/82780#82780

J'ai posté la question dans le lien ci-dessus, et je ne comprends pas bien la réponse que je veux. La réponse fournie dans le lien serait correcte si un nombre peut commencer par 0. Mais je tiens à souligner que ce n'est pas autorisé. Le langage décrit ici est l'ensemble des entiers tels que la somme des chiffres est un multiple de deux. Ou de manière équivalente, un ensemble de nombres qui a un nombre pair de chiffres impairs (par exemple 2354 a deux nombres impairs 3,5). Comment puis-je dériver une expression régulière pour une telle langue? Toute idée supplémentaire serait appréciée.

Answer 1

Supposons que vous avez déjà trouvé un entier pair. Ensuite, vous pouvez prolonger arbitrairement soit

• ajoutant un chiffre pair ou
• ajoutant un chiffre impair, suivi de 0 ou plus même chiffres, suivi d'un chiffre impair

Le résultat sera être un autre entier pair.

Maintenant, nous avons juste besoin d'un moyen de commencer. Un entier pair somme commence avec soit

• un chiffre pair qui ne soit pas 0, ou
• un chiffre impair, suivi de 0 ou plus, même chiffres, suivi par un chiffre impair

Nous peut écrire ceci comme une regex:

([2468]|[13579][02468]*[13579])([02468]|[13579][02468]*[13579])*