L={a^nb^m| n+m=k ,n,m>=0} with Regular Expression in C#

Question

I want To generate the following language:

L={a^nb^m| n+m=k ,n,m>=0}

for a constant k.

I'm using the class Regex of namespace System.Text.RegularExpressions.

The best solution I have right now is:

public void Match(string input, int k)
{
    Regex regex = new Regex(@"a*b*");
    Match match = regex.Match(input);
    if(match.Length==k)
        Console.WriteLine("Successfully");
    else
        Console.WriteLine("Don't match");
}

For k=5 the following inputs are successfully:

"aaabb"
"aabbb"
"aaaaa"

This one for example is not:

"aaabbb"
"ab"

What's the most elegant way to achieve this?

Answer 1

You can achieve it using look aheads

For k = 5

/^(?=.{5}$)a*b*$/

• (?=.{5}$) Positve look ahead. Ensures that string contains only 5 characters.

• a*b* matches zero or more occurence of a followed by zero or more occurence b

Regex Demo

Test

public static void Match(string input, int k)
{
    Regex regex = new Regex(@"^(?=.{"+k+"}$)a*b*$");
    Console.WriteLine(regex.IsMatch(input));

}

---

Match("aaabb", 5);
=> True
Match("aaabbb", 5);
=> False

Answer 2

nu11p01n73R's answer uses look-ahead, which is commonly used in practical regex, but is not part of theoretical regular expression (where concatenation, alternation, and Kleene stars are the only operators available).

There is no clean solution in theoretical regular expression for this case. You can only list all the cases. For example, if k = 5:

aaaaa|aaaab|aaabb|aabbb|abbbb|bbbbb

You can at most shorten it a bit by grouping:

aaa(aa|ab|bb)|(aa|ab|bb)bbb

The language is regular. k is a constant, so we can always draw a state machine with 2k + 1 states.

An example for k = 5:

Missing transitions goes to a trap state which is not an accepting state.