Expression régulière dont la longueur de chaîne est une puissance de 2

Question

Donc cette question n'est spécifique à aucun langage de programmation mais à des expressions régulières en termes de langage, c'est pour un cours de pragmatique en langage de programmation. Tout ce que j'ai à utiliser est (), *(zero or more occurance), +(one or more occurance), | et les puissances.

Si l'alphabet est {a,b}, quelle serait l'expression régulière pour le langage où les longueurs de chaîne sont des puissances de 2, donc 2^n pour n> = 1. dire aa, abba, bbaabbbb

si ((a|b)(a|b))+ donnerions cordes de même longueur> = 2

Answer 1

Ouais j'ai parlé avec d'autres personnes, il est impossible. Juste comme si vous vouliez qu'il y ait le même nombre de a et b, ne peut pas le faire.

Answer 2

Les expressions régulières sont reconnues par les machines à états finis, alors que cette langue est un langage décidable (ce qui signifie qu'elle est acceptée par une machine de Turing).