Ця відповідь пояснює теоретичне обмеження того, чому регулярні вирази не є придатним інструментом для цього завдання.

Регулярні вирази не можуть цього зробити.

Регулярні вирази засновані на обчислювальної моделі, відомої як Finite State Automata (FSA). Як видно з назви, FSA може запам'ятати тільки поточний стан, у нього немає інформації про попередні станах.

На поступовим зниженням дози S1 і S2 - це два стани, де S1 - початковий і останній етап. Так що, якщо ми спробуємо з рядком 0110, перехід буде виглядати наступним чином:

0 1 1 0 -> S1 -> S2 -> S2 -> S2 -> S1

На вищенаведених етапах, коли ми знаходимося на другому S2 тобто після аналізу 01 з 0110, FSA не має інформації про попередні 0 в 01 оскільки він може тільки запам'ятати поточний стан і наступний вхідний символ.

У вищезгаданій проблемі нам потрібно знати номер відкриває дужки; це означає, що він повинен зберігатися в якомусь місці. Але оскільки FSAs не може цього зробити, регулярний вираз не може бути написано.

Однак для цього завдання можна написати алгоритм. Алгоритми зазвичай підпадають під Pushdown Automata (PDA). PDA на один рівень вище FSA. КПК має додатковий стек для зберігання додаткової інформації. КПК можуть бути використані для вирішення зазначеної вище проблеми, тому що ми можемо "push" відкриття дужка в стеку і "pop" їх, коли ми зіткнулися з закриваючою дужкою. Якщо в кінці стек порожній, то що відкриваються і закриваються дужки збігаються. В іншому випадку немає.