Соответствие ^ n A ^ n с регулярным выражением

Question

Мы узнаем о разнице между обычными языками и регулярными выражениями, и учитель объяснил, что язык

a^n b^n

не является регулярным, но она сказала, что большинство регулярных выражений могут соответствовать

a^n A^n

и она дала эту проблему за нашу дополнительную домашнюю задачу. Мы боролись в течение нескольких дней и могли бы действительно использовать некоторые рекомендации.

Answer 1

Учитель дал ОГРОМНЫЙ намек, ограничив алфавит до {a, A}.Ключом к решению этой проблемы является понимание того, что в режиме без учета регистра a соответствует A и наоборот.Другой компонент проблемы совпадает с обратной ссылкой.

Этот шаблон будет соответствовать a{n}A{n} для некоторых n (, как видно на rubular.com ):

^(?=(a*)A*$)\1(?i)\1$

---

Как это работает

Шаблон работает следующим образом:

• ^(?=(a*)A*$) - Якорь в начале строки, мы используем положительный прогноз, чтобы увидеть, если мыможет соответствовать (a*)A* до конца строки
  • Если мы можем успешно сделать это утверждение, то \1 фиксирует последовательность a{n}
  • Если утверждение не выполнено, то нетТаким образом, строка может быть a{n}A{n}, поскольку она даже не a*A*
• Затем мы сопоставляем \1(?i)\1$, то есть a{n}, захваченное \1, затем в режиме без учета регистра (?i), мы сопоставляем a{n} снова до конца строки
• Таким образом, так как:
  • Строка a*A*
  • \1 is a{n}
  • \1(?i)\1 может быть только a{n}A{n}

Смежные вопросы

• Case seнечувствителен и нечувствителен в одном шаблоне
• Как работает регулярное выражение '(? <= #) [^ #] + (? = #)'? </a>

Ссылки

• регулярные-выражения.info / Lookaround , Группировка и обратные ссылки
• Модификаторы (особенно Включение и выключение режимов только для части регулярного выражения )

См. Также

• Почему {a ^ nb ^ n|n> = 0} не регулярно?
• Википедия / Регулярное выражение: шаблоны для нерегулярных языков