CODEWITHSUNDEEP
regex
arnoapp
arnoapp

Reputation: 2486

Regular expression with a given length with an exact number of a character

I'm looking for a regular expression for the language $w\in {a,b}^n$ 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 ${{b}^*a{b}^*}^k$.

Does anybody have any advice on how I can achieve such an regex?

Upvotes: 3

Views: 134

Answers (3)

Bohemian
Bohemian

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

Bergi
Bergi

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

deufeufeu
deufeufeu

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

Related Questions