Вы натолкнулись на действительно важную идею в теории формального языка - чистые / теоретические регулярные выражения не могут соответствовать языку a ^ n b ^ n! Это важный результат. Теорема Майхилла-Нерода - хороший способ понять, почему это так, но, в основном, она сводится к следующему: если вы можете показать, что ни один конечный автомат не может принять язык, он не является регулярным и не имеет регулярного выражения.
В частности, для вашего языка предположим, что он регулярный и есть регулярное выражение. Затем мы знаем, что существует детерминированный конечный автомат, который принимает язык. Далее можно сделать вывод, что существует детерминированный конечный автомат с как можно меньшим числом состояний - минимальный DFA. Пусть число состояний в этом DFA будет p. Теперь рассмотрим строку a ^ p b ^ p на нашем языке. Поскольку число состояний равно p, а длина строки больше, чем p-1, DFA должен был зацикливаться в какой-то момент при обработке этой строки длиной 2p. Пусть x будет подстрокой a ^ p b ^ p, обработанной при прохождении этого цикла. Затем, поскольку наш DFA принимает a ^ p b ^ p, он также должен принимать любую строку, полученную путем обхода цикла любое количество раз или вообще без его обхода. То есть мы можем избавиться от подстроки x или изменить ее на x ^ 2 или x ^ k, и эта строка также должна быть на нашем языке. Есть ли выбор для х, который работает для нас? Оказывается, что нет - независимо от того, какую подстроку мы выбираем ^ pb ^ p, изменение числа вхождений дает нам строку не на нашем языке (либо она меняет только число a, но только число b). или порядок a и b посередине). Поэтому нашего DFA не существует и поэтому нет регулярных выражений. По сути, это длинное доказательство из-за леммы прокачки для обычных языков, еще один инструмент.
Наименее способной (канонической) системой вычислений, способной описать язык a ^ n b ^ n, является класс контекстно-свободных языков. Контекстные грамматики могут использоваться для описания того, как генерируются эти языки. CFG для вашего языка это:
S -> aSb
S -> epsilon
Способ использования этого состоит в том, чтобы начать с S (нетерминальный начальный символ), а затем использовать произведения (правила отображения) для получения промежуточных выражений, пока у вас не останется строка только из терминальных символов (наши терминальные символы являются и б). Мы можем сгенерировать aaabbb как S -> aSb -> aaSbb -> aaaSbbb -> aaabbb.
Теперь, если вы спрашиваете о прикладном программировании с использованием библиотек "regex", они, как правило, предлагают больше функций, позволяющих захватывать нерегулярные языки. Вероятно, они сделали эти безбожные чудовища эквивалентными Тьюрингу, проверив GitHub на наличие реализаций Quake, построенных только на «регулярных выражениях».