This question wants me to write a regular expression over the following language:
L = {w | w has exactly two a's and at least three b's}
(and the alphabet is {a,b})
I have dealt with this by drawing it's NDA at first and then writing a regular expression for my NDA. But it's way harder than I thought and probably not working for this question.
My NDA (which I think is incorrect):
So far the regular expression I came up with seems way too long (to answer the need for exactly two a's and at least three b's. I considered every possible premutation for minimum requirements)
Am I doing it in a correct way? Or, Is there any way to answer this question without drawing NDA?
Best Answer
It is in fact trivially possible to make a DFA for the language with $13$ states, $12$ corresponding to "seen $i$ a's and $j$ b's" where $0\le i\le2$ and $0\le j\le 3$ and one reject state. Making a regular expression, though, does require casework on the possible permutations of b's among the (considered fixed) a's; there are $10$ ways to distribute three b's in the three spaces (left, middle and right), and they force $10$ different subexpressions without union: $$\mathtt{b+ab+ab+|b++ab+a|b+ab++a|b++aab+|b+aab++|ab++ab+|ab+ab++|b+++aa|ab+++a|aab+++}$$ where $\mathtt{b+}^n$ is shorthand for $\mathtt b^n\mathtt{b*}$.