☰

Возможно ли выполнить egrep этих симметричных выражений над {0,1}?

tag-icon • tag-icon grep
Возможно ли выполнить egrep этих симметричных выражений над {0,1}?

Цель состоит в том, чтобы использовать исключительно egrep для сопоставления выражений, гденза вхождениями 0 следует ровнонвхождения 1 и случаи, когда за 1 не следует 0.

например

01
000111
000000111111

но нет:

001
011
00011

и т. д.

Интуитивно это кажется недостижимым, поскольку сопоставляемые выражения не имеют фиксированной длины. Но, возможно, я упускаю какую-то функцию egrep, которая могла бы быть полезной в этом случае?

решение1

Краткий обзор некоторых концепций CS:

  • Автоматыпринимать строки, принадлежащие «языку»,сгенерированный «грамматикой».
  • Регулярные выражения (теоретически) эквивалентны (детерминированным или недетерминированным)конечные автоматы(DFA/NFA). Итак, если задано регулярное выражение, например 0*1*, существуют DFA и NFA, которые могут принимать строки, соответствующие этому регулярному выражению.
  • Конечные автоматы строго менее мощные, чемавтоматы с выталкивателем(PDA). Класс языков, которые принимает PDA, генерируетсяКонтекстно-свободные грамматики (CFG).
  • Строки, на которые вы смотрите, генерируются CFG: (грубо говоря, имея начальную строку, вы можете сгенерировать строку с и по обе стороны от исходной строки или без них — то есть он позволяет вам генерировать , и т. д.).0n1nS -> 0S1 | ε01010011

Хотя grep (расширенный или нет) обладает функциями, выходящими за рамки упомянутых выше «регулярных выражений», такими как обратные ссылки, я не верю, что какие-либо из них расширяют его возможности до уровня PDA.

Можно доказать, что S -> 0S1 | εне является регулярным, используялемма о накачке, но у меня нет доказательств того, что функции grep позволяют (или не позволяют) принимать CFG. Однако статья в Википедии оОбычные выраженияесть что сказать (выделено жирным шрифтом):

Многие функции, которые можно найти практически во всех современных библиотеках регулярных выражений, обеспечивают выразительную силу, которая намного превосходит обычные языки. Например, многие реализации позволяют группировать подвыражения с помощью скобок и вызывать значение, которому они соответствуют в том же выражении (обратные ссылки). Это означает, что, помимо прочего, шаблон может соответствовать строкам повторяющихся слов, таких как "papa" или "WikiWiki", называемым квадратами в формальной теории языка. Шаблон для этих строк — (.+)\1.

Язык квадратов не является регулярным,и это не является контекстно-свободным, из-за леммы о накачке. Однако сопоставление с образцом с неограниченным числом обратных ссылок, поддерживаемое многочисленными современными инструментами, по-прежнему зависит от контекста. [33]

[33]: Cezar Câmpeanu и Kai Salomaa, и Sheng Yu (декабрь 2003 г.). "Формальное исследование практических регулярных выражений". International Journal of Foundations of Computer Science. 14 (6): 1007–1018. doi:10.1142/S012905410300214X. Теорема 3 (стр. 9)

Поэтому я бы с уверенностью сказал, что само по себе grepэто не сравнится .0n1n

Связанный контент