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

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

Строки и языки

Строка — это конечная последовательность символов. строка Пустая обозначается $\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 ∈ Σ. Замены строк могут быть распространены на целые языки как

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

Обычные языки закрыты при подстановке строк. То есть, если каждый символ в алфавите обычного языка заменить другим регулярным языком, результатом по-прежнему будет регулярный язык. Аналогично, контекстно-свободные языки закрыты при подстановке строк.

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

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

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

• f _uc (‹Straße›) = {‹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$.

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

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

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

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

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

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

и

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

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

Класс регулярных языков замкнут относительно гомоморфизмов и обратных гомоморфизмов. Аналогично, контекстно-свободные языки замкнуты относительно гомоморфизмов и обратные гомоморфизмы.

Строковый гомоморфизм называется ε-свободным (или 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 ₁ } . Это не обобщение приведенного выше определения, поскольку для строки s и различных символов a , b определение Хопкрофта и Ульмана подразумевает получение {}, а не {ε}.

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

Синтаксическое отношение

Правильное частное подмножества $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)$. Это отношение является частным примером префиксного порядка .

См. также

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

Ссылки

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