Reputation: 2486
I'm looking for a regular expression for the language with the exact number of k a's in it.
I'm pretty much stuck at this. For a various length the solution would be easy with .
Does anybody have any advice on how I can achieve such an regex?
Upvotes: 3
Views: 134
Reputation: 425448
You can use a look ahead to enforce the overall length:
^(?=.{5}$)([^a]*a){2}[^a]*$
See this demonstrated on rubular
Upvotes: 0
Reputation: 665574
There is no simple solution to this.
While that language is regular, it's ugly to describe. You can get it by intersecting the (trivial) DFAs for both languages ((a|b)^n
and b*(ab*)^k
) with each other, but you'll get a DFA with (n-k)*k
states back. And transforming that it into a regular expression won't make it better.
However, if you're looking for an actual implementation it gets much easier. You can simply test the input against both regexes, or you can use lookahead to compose them into one regex:
/^(?=[ab]{n}$)b*(ab*){k}$/
Upvotes: 1
Reputation: 1008
I'd use this one :
(b*ab*){k}
It just makes k blocks containing exactly one a. Therefore words have k a. One of the b* can be factored out on the left or on the right.
Upvotes: 2