Операции со строками

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

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

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

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

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

Например, сокращая , множество всех трехзначных десятичных чисел получается как . Множество всех десятичных чисел произвольной длины является примером для бесконечного языка.${\displaystyle 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 \}}$${\displaystyle D\cdot D\cdot D}$

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

${\displaystyle \operatorname {Alph} (s)}$

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

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

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

f (ε)=ε

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

f ( sa )= f ( s ) f ( a )

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

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

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

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

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

• f _uc (‹Штрассе›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹ШТРАССЕ›},
• f _uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, и
• f _uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Для расширения f _uc на языки мы имеем, например,

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

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

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

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

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

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

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

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

и

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

для любого языка .${\displaystyle L}$

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

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

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

• g _uc ⁻¹ ({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, так как g _uc (‹sss›) = g _uc (‹sß›) = g _uc (‹ßs›) = ‹SSS›, и
• g _uc ⁻¹ ({ ‹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 — строка, а — алфавит, строковая проекция s — это строка, которая получается путем удаления всех символов, отсутствующих в . Она записывается как . Формально она определяется путем удаления символов с правой стороны:${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \pi _{\Sigma }(s)\,}$

${\displaystyle \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}}}$

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

Проекция строки может быть повышена до проекции языка . Если задан формальный язык L , его проекция задается как

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$^{[ необходима ссылка ]}

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

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

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

${\displaystyle \varepsilon /a=\varepsilon }$

Аналогично, если задано подмножество моноида , можно определить фактор-подмножество как${\displaystyle S\subset M}$${\displaystyle M}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \varepsilon \div a=\varepsilon }$

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

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$^{[ необходима ссылка ]}

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

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

где .${\displaystyle s\in L}$

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

${\displaystyle \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\}}$

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

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

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

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

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

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

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