Регулярные выражения (регулярные выражения) действительно регулярны?
Я понимаю, как регулярные выражения получили свое имя, и прочитал соответствующий вопрос ( Почему регулярные выражения называются "регулярными" выражениями?), Но все еще задаюсь вопросом, всегда ли регулярные выражения являются регулярными.
Например, как обратные ссылки могут быть регулярными? Разве это не потребует некоторой памяти и, следовательно, будет невозможно сопоставить / сгенерировать автоматом конечных состояний?
2 ответа
Ссылка в ответе на вопрос, на который вы ссылаетесь, указана (в википедии), в отличие от многих механизмов регулярных выражений, предоставляемых современными языками программирования, которые дополнены функциями, позволяющими распознавать языки, которые не могут быть выражены классическим регулярным выражением.
Поэтому я бы сказал, что эволюция регулярных выражений отодвинула его от первоначальной идеи выражения регулярных языков.
Из статьи Википедии о регулярных выражениях:
Многие функции, присутствующие практически во всех современных библиотеках регулярных выражений, обеспечивают выразительную силу, которая намного превосходит обычные языки. Например, многие реализации позволяют группировать подвыражения с круглыми скобками и вызывать соответствующие им значения в одном выражении (обратные ссылки). Это означает, что, среди прочего, шаблон может соответствовать цепочкам повторяющихся слов, таких как "папа" или "WikiWiki", называемых квадратами в теории формального языка. Шаблон для этих строк
(.+)\1,
Современные расширения, включая обратные ссылки, делают системы регулярных выражений кандидатом не в обычные языки, однако IMO они могут быть перенесены на контекстно-свободные языки, но не на машины Тьюринга.
Регулярные грамматики имеют общее свойство, называемое леммой прокачки. Вы можете проверить пример здесь, который доказывает, что 0n1n не является обычной грамматикой (что очень похоже на обратные ссылки). Вот как можно показать, что обратные ссылки не удовлетворяют свойству леммы прокачки.
Насыщенная лемма в текущем контексте: чтобы показать, что система регулярных выражений является регулярной грамматикой, должна быть конечная длина p, такая, что все строки, которые соответствуют регулярному выражению и имеют длину, равную или большую, чем p, могут быть разделены на три подстроки xyz, такие как что y не является пустой строкой, и все строки, представленные xy* z (y закачаны в течение [0, бесконечно) раз), совпадают с регулярным выражением.
Если мы не можем показать, что такое p не может удовлетворить условиям для регулярного выражения, то оно не входит в регулярную грамматику.
Для обратных ссылок нам понадобятся две из этих строк накачки, которые тоже имеют одинаковую длину, одну для подшаблона в захваченной группе и одну в обратной ссылке. Это как раз то, что представляют собой автоматные или контекстно-свободные языки. Существует также лемма прокачки для контекстно-свободных грамматик, которая основана на разбиении на uvwxy, где v и x могут быть прокачаны одинаково n раз. Мы можем показать, что регулярное выражение с системой обратных ссылок удовлетворяет этой лемме.