Строковые операции

В информатике , в области теории формального языка , часто используются различные строковые функции ; однако используемые обозначения отличаются от обозначений, используемых для компьютерного программирования , а некоторые часто используемые в теоретической области функции редко используются при программировании. В этой статье даны определения некоторых из этих основных терминов.

Строки и языки [ править ]

Строка — это конечная последовательность символов. Пустая строка обозначается $\varepsilon$ . Объединение двух строк $s$ и $t$ обозначается $s\cdot t$ , или короче на $st$ . Объединение с пустой строкой не имеет значения: $s\cdot \varepsilon =s=\varepsilon \cdot s$ . Объединение строк ассоциативно : $s\cdot (t\cdot u)=(s\cdot t)\cdot u$ .

Например, $(\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle$ .

Язык — это конечный или бесконечный набор строк. Помимо обычных операций над множествами, таких как объединение, пересечение и т. д., к языкам можно применять конкатенацию: если оба $S$ и $T$ это языки, их конкатенация $S\cdot T$ определяется как набор конкатенаций любой строки из $S$ и любая строка из $T$ , формально $S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}$ . И снова точка конкатенации $\cdot$ часто опускается для краткости.

Язык $\{\varepsilon \}$ состоящий только из пустой строки, следует отличать от пустого языка $\{\}$ . Объединение любого языка с первым не вносит никаких изменений: $S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S$ , в то время как объединение с последним всегда дает пустой язык: $S\cdot \{\}=\{\}=\{\}\cdot S$ . Объединение языков ассоциативно: $S\cdot (T\cdot U)=(S\cdot T)\cdot U$ .

Например, сокращая $D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}$ , набор всех трехзначных десятичных чисел получается как $D\cdot D\cdot D$ . Набор всех десятичных чисел произвольной длины является примером бесконечного языка.

Алфавит строки [ править ]

Алфавит строки — это набор всех символов, встречающихся в конкретной строке. Если s — строка, ее алфавит обозначается

\operatorname {Alph} (s)

Алфавит языка $S$ это набор всех символов, которые встречаются в любой строке $S$ , формально: $\operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)$ .

Например, набор $\{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}$ это алфавит строки $\langle cacao\rangle$ , и вышеизложенное $D$ это алфавит вышеуказанного языка $D\cdot D\cdot D$ а также языка всех десятичных чисел.

Замена строки [ править ]

Пусть L — язык , и пусть Σ — его алфавит. Подстановка строк или просто замена — это отображение f , которое отображает символы из Σ в языки (возможно, в другом алфавите). Так, например, для характера a ∈ Σ имеем f ( a ) = L _a , где L _a ⊆ ∆ ^*— некоторый язык, алфавит которого равен Δ. Это отображение может быть расширено на строки как

е (е)=е

для пустой строки ε и

ж ( са ) = ж ( s ) ж ( а )

для строки s ∈ L и символа a ∈ Σ. Замены строк могут быть распространены на целые языки как ^[1]

f(L)=\bigcup _{s\in L}f(s)

Обычные языки закрыты при подстановке строк. То есть, если каждый символ в алфавите обычного языка заменить другим регулярным языком, результатом по-прежнему будет регулярный язык. ^[2] Аналогично, контекстно-свободные языки закрыты при подстановке строк. ^[3]^{[примечание 1]}

Простым примером является преобразование f _uc (.) в верхний регистр, которое можно определить, например, следующим образом:

характер	сопоставлен с языком	замечание
Икс	фу _ук ( х )
‹ а ›	{ ‹ А › }	сопоставить символ нижнего регистра с соответствующим символом верхнего регистра
‹ А ›	{ ‹ А › }	сопоставить прописные символы с самим собой
< SS >	{ < SS > }	нет символов в верхнем регистре, отображается строка из двух символов
‹0›	{ е }	сопоставить цифру с пустой строкой
‹!›	{ }	запретить знаки препинания, сопоставить пустой язык
...		аналогично для других персонажей

Для расширения fuc _, на строки мы имеем, например

f _uc (‹Street›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹ДОРОГА›},
f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, и
f _uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Для распространения fuc _, на языки мы имеем, например

f _uc ({ ‹Штрассе›, ‹u2›, ‹Go!› }) = { ‹ШТРАССЕ› } ∪ { ‹U› } ∪ { } = { ‹ШТРАССЕ›, ‹U› }.

Строковый гомоморфизм [ править ]

Строковый гомоморфизм (часто называемый просто гомоморфизмом в теории формального языка ) — это строковая замена, при которой каждый символ заменяется одной строкой. То есть, $f(a)=s$ , где $s$ это строка для каждого символа $a$ . ^{[заметка 2]}^[4]

Строковые гомоморфизмы — это моноидные морфизмы на свободном моноиде , сохраняющие пустую строку и бинарную операцию конкатенации строк . Учитывая язык $L$ , набор $f(L)$ называется образом гомоморфным $L$ . Обратный гомоморфный образ строки $s$ определяется как

$f^{-1}(s)=\{w|f(w)=s\}$

а обратный гомоморфный образ языка $L$ определяется как

$f^{-1}(L)=\{s|f(s)\in L\}$

В общем, $f(f^{-1}(L))\neq L$ , хотя у человека есть

$f(f^{-1}(L))\subseteq L$

и

$L\subseteq f^{-1}(f(L))$

для любого языка $L$ .

Класс регулярных языков замкнут относительно гомоморфизмов и обратных гомоморфизмов. ^[5] Аналогично, контекстно-свободные языки замкнуты относительно гомоморфизмов ^{[заметка 3]} и обратные гомоморфизмы. ^[6]

Строковый гомоморфизм называется ε-свободным (или e-свободным), если $f(a)\neq \varepsilon$ для всех а в алфавите $\Sigma$ . Простые однобуквенные шифры замены являются примерами (ε-свободных) гомоморфизмов строк.

Пример гомоморфизма строк g _uc также можно получить, задав аналогичную вышеописанной замену: g _uc (‹a›) = ‹A›, ..., g _uc (‹0›) = ε, но позволив g _uc быть неопределенным о знаках препинания. Примеры обратных гомоморфных изображений:

г _ук⁻¹({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, так как g _uc (‹sss›) = g _uc (‹ss›) = g _uc (‹ßs›) = ‹SSS› , и
г _ук⁻¹({ ‹A›, ‹bb› }) = { ‹a› }, так как g _uc (‹a›) = ‹A›, а ‹bb› не может быть достигнуто с помощью g _uc .

Для последнего языка g _uc ( g _uc⁻¹({ ‹A›, ‹bb› })) = g _uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. Гомоморфизм g _uc не является ε-свободным, поскольку он отображает, например, ‹0› в ε.

Очень простой пример гомоморфизма строк, который отображает каждый символ только в символ, — это преобразование строки в кодировке EBCDIC в ASCII .

Струнная проекция [ править ]

Если s — строка и $\Sigma$ — это алфавит, строковая проекция s — это строка , полученная в результате удаления всех символов, отсутствующих в $\Sigma$ . Это написано как $\pi _{\Sigma }(s)\,$ . Формально это определяется удалением символов из правой части:

\pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}

Здесь $\varepsilon$ обозначает пустую строку . Проекция строки по существу аналогична проекции в реляционной алгебре .

Проекцию строки можно превратить в проекцию языка . Учитывая формальный язык L , его проекция задается формулой

\pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}

^{[ нужна цитата ]}

Правое и левое частное [ править ]

Правое частное символа a из строки s — это усечение символа a в строке s с правой стороны. Он обозначается как $s/a$ . Если строка не имеет справа , результатом будет пустая строка. Таким образом:

(sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}

Частное пустой строки может быть взято:

\varepsilon /a=\varepsilon

Аналогично, учитывая подмножество $S\subset M$ моноида $M$ , можно определить факторподмножество как

S/a=\{s\in M\ \vert \ sa\in S\}

Левые частные могут быть определены аналогичным образом, при этом операции выполняются слева от строки. ^{[ нужна цитата ]}

Хопкрофт и Ульман (1979) определяют фактор L ₁ / L ₂ языков L ₁ и L ₂ по одному и тому же алфавиту как L ₁ / L ₂ = { s | ∃ т ∈ L ₂ . ст ∈ L ₁ } . ^[7] Это не обобщение приведенного выше определения, поскольку для строки s и различных символов a , b определение Хопкрофта и Ульмана подразумевает получение {}, а не {ε}.

Левое частное (если оно определено аналогично Хопкрофту и Ульману, 1979) одноэлементного языка L ₁ и произвольного языка L ₂ известно как производная Бжозовского ; если L ₂ представлен регулярным выражением , то же самое может быть и левым частным. ^[8]

Синтаксическое отношение [ править ]

Правильное частное подмножества $S\subset M$ моноида $M$ определяет отношение эквивалентности называемое правым синтаксическим S. , отношением Это дано

\sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}

Очевидно, что отношение имеет конечный индекс (имеет конечное число классов эквивалентности) тогда и только тогда, когда правые факторы семейства конечны; то есть, если

\{S/m\ \vert \ m\in M\}

конечно. В случае, когда M — моноид слов в некотором алфавите, S — регулярный язык , то есть язык, который может распознаваться конечным автоматом . Подробнее об этом говорится в статье о синтаксических моноидах . ^{[ нужна цитата ]}

Право отмены [ править ]

Правое удаление символа a из строки s — это удаление первого вхождения символа a в строку s , начиная с правой части. Он обозначается как $s\div a$ и рекурсивно определяется как

(sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}

Пустую строку всегда можно отменить:

\varepsilon \div a=\varepsilon

Очевидно, что правая отмена и проекция коммутируют :

\pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)

^{[ нужна цитата ]}

Префиксы [ править ]

Префиксы строки — это набор всех префиксов строки относительно данного языка:

\operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}

где $s\in L$ .

Префиксное языка закрытие

\operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}

Пример:
$L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}$

Язык называется префиксно-закрытым , если $\operatorname {Pref} (L)=L$ .

Оператор закрытия префикса идемпотентен :

\operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)

Префиксное отношение является бинарным отношением $\sqsubseteq$ такой, что $s\sqsubseteq t$ если и только если $s\in \operatorname {Pref} _{L}(t)$ . Это отношение является частным примером префиксного порядка . ^{[ нужна цитата ]}

См. также [ править ]

Сравнение языков программирования (строковые функции)
Лемма Леви
Строка (информатика) — определение и реализация более простых операций со строками.

Примечания [ править ]

^ Хотя каждый регулярный язык также является контекстно-свободным, предыдущая теорема не подразумевается текущей, поскольку первая дает формирующий результат для регулярных языков.
^ Строго формально гомоморфизм дает язык, состоящий всего из одной строки, т.е. $f(a)={s}$ .
^ Это следует из упомянутого выше замыкания при произвольных заменах.

Ссылки [ править ]

Хопкрофт, Джон Э.; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Ридинг, Массачусетс: Издательство Addison-Wesley. ISBN 978-0-201-02988-8 . Збл 0426.68001 . (См. главу 3.)

^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60
^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.4, стр.60
^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.2, стр. 131
^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60-61.
^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.5, стр.61
^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.3, стр. 132
^ Хопкрофт, Ульман (1979), раздел 3.2, стр.62
^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .

[4] Хотя каждый регулярный язык также является контекстно-свободным, предыдущая теорема не подразумевается текущей, поскольку первая дает формирующий результат для регулярных языков.

[singleton_sets-5] Строго формально гомоморфизм дает язык, состоящий всего из одной строки, т.е. $f(a)={s}$ .

[8] Это следует из упомянутого выше замыкания при произвольных заменах.

[1] Хопкрофт, Ульман (1979), раздел 3.2, стр.60

[2] Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.4, стр.60

[3] Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.2, стр. 131

[6] Хопкрофт, Ульман (1979), раздел 3.2, стр.60-61.

[7] Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.5, стр.61

[9] Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.3, стр. 132

[10] Хопкрофт, Ульман (1979), раздел 3.2, стр.62

[11] Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .

[1]

[2]

[3]

[примечание 1]

[заметка 2]

[4]

[5]

[заметка 3]

[6]

[7]

[8]

v т Это Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Три
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции