5

I'm learning about regular expressions and how they represent regular languages of an alphabet. Conceptually, I'm having trouble imagining what a regular expression would look like, representing a language that has at least x amount of a's and y amount of b's, for example, in an alphabet {a,b}.

The way I understand it, if the question was, for example, a regular expression representing the language with at least one of each, the regular expression would look like $a^*b^*(ab+ba)a^*b^*$ ... But this doesn't seem very efficient. I know that if you have a regular expression $(ab)^*$, the language does not include the word ba, yet once the the "least number" of letters in the alphabet increases, the length of the expression roughly increases exponentially! I'm aware of the "+" symbol, but wouldn't that have the same problem as star when applying it to "at least 1 of each" problems?

Say, for the regular expression representing the language with at least two a's and b's, it seems excessive to write $a^*b^*(aabb+abab+bbaa+baba+baab+abba)a^*b^*$. I'm confused because I feel like there has to be a simpler way to write the expression, but I can't seem to find a solution. If there is a simpler way to write it, is the example I use still valid?

J.-E. Pin
  • 38,183
  • 3
  • 33
  • 84
Nick Borisenko
  • 151
  • 3
  • Sadly you cannot avoid the exponential blow up for you required regular expressions, because you have to keep track of all the possible interleaving of the a's and b's. However the example you give does not seems right since it does not match baaaaaaaaab for example. I would go for $(aaa^*ba^*b+abaa^*b+abbb^*a+babb^*a+baaa^*b+bbb^*ab^*a)(a+b)^*$ instead – wece Dec 09 '15 at 09:47
  • I edited your post, but there is still one change to be made: every occurrence of $a^*b^*$ should be changed to $(a + b)^*$. – J.-E. Pin Dec 09 '15 at 12:32
  • @wece Why don't you make your comment an answer ? You could just add the way you found this expression, probably by using the DFA for $A^*aA^*aA^* \cap A^*bA^*bA^*$, where $A = \{a,b\}$. – J.-E. Pin Dec 09 '15 at 12:35
  • Oh yea that makes sense - forgot to consider that! If you would post that as the answer I would accept it (: – Nick Borisenko Dec 09 '15 at 23:14

1 Answers1

2

Sadly you cannot avoid the exponential blow up for you required regular expressions, because you have to keep track of all the possible interleaving of the a's and b's. However the example you give does not seems right since it does not match baaaaaaaaab for example. I would go for $$(aaa^∗ba^∗b+abaa^∗b+abbb^∗a+babb^∗a+baaa^∗b+bbb^∗ab^∗a)(a+b)^∗$$ instead

wece
  • 2,702
  • 1
  • 14
  • 26