L = {a^nb^m | п + т = к, п, т> = 0} с использованием регулярных выражений в C#

Question

Я хочу, чтобы генерировать следующий язык:

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

для постоянного k.

Я использую класс Regex пространства имен System.Text.RegularExpressions.

Лучшее решение я прямо сейчас:

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"); 
} 

Для k=5 следующие входы успешно:

"aaabb" 
"aabbb" 
"aaaaa" 

Это один, например, не является:

"aaabbb" 
"ab" 

Что самый элегантный способ добиться этого?

Answer 1

Вы можете достичь его, используя внешний вид aheads

Для k = 5

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

• (?=.{5}$) Positve смотреть вперед. Обеспечивает, чтобы строка содержала только 5 символов.

• a*b* соответствует нулю или более вхождение a с последующим нулем или более вхождение 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 использует внешний вид, который обычно используется в практическом регулярном выражении, но не является частью теоретического регулярного выражения (где единственными доступными являются конкатенация, чередование и звезды Клейна).

В этом случае нет чистого решения теоретического регулярного выражения. Вы можете только перечислить все случаи. Например, если к = 5:

aaaaa|aaaab|aaabb|aabbb|abbbb|bbbbb 

Вы можете максимально сократить его немного с помощью группирования:

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

язык является регулярным. k является константой, поэтому мы можем всегда рисовать машину состояний с 2k + 1 состояниями.

В качестве примера для к = 5:

Отсутствующих переходы переходит в состояние ловушки, которое не является принимающим состоянием.