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

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

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

Строка — это конечная последовательность символов. Пустая строка обозначается как . Конкатенация двух строк и обозначается как , или короче как . Конкатенация с пустой строкой не имеет значения: . Конкатенация строк ассоциативна : . ${\displaystyle \varepsilon }$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s\cdot t}$ ${\displaystyle st}$ ${\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 T}$ ${\displaystyle S\cdot T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\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)}$

Смотрите также

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

Примечания

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

Ссылки

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

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