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

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

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

Строка - это конечная последовательность символов. пустой строкой обозначается ${\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 быть язык, и пусть Σ его алфавит. А подстановка строк или просто замена это отображение ж который отображает символы в Σ на языки (возможно, в другом алфавите). Так, например, с учетом персонажа а ∈ Σ, имеем ж(а)=L_а куда L_а ⊆ Δ^* - некоторый язык с алфавитом Δ. Это отображение может быть расширено до строк как

ж(ε) = ε

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

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

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

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

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

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

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

Для продления ж_uc к строкам у нас есть, например,

• ж_uc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• ж_uc(‹U2›) = {‹U›} ⋅ {ε} = {‹U›} и
• ж_uc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Для продления ж_uc к языкам у нас есть, например,

• ж_uc({‹Straße›, ‹u2›, ‹Go!›}) = {‹STRASSE›} ∪ {‹U›} ∪ {} = {‹STRASSE›, ‹U›}.

Гомоморфизм струн

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

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

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

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

${\displaystyle f^{-1}(L)=\{s|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-свободным), если ${\displaystyle f(a)\neq \varepsilon }$ для всех а в алфавите ${\displaystyle \Sigma }$. Простая однобуквенная подстановочные шифры являются примерами (ε-свободных) гомоморфизмов струн.

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

• грамм_uc⁻¹({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›}, поскольку грамм_uc(‹Sss›) = грамм_uc(‹Sß›) = грамм_uc(‹Sss›) = ‹SSS› и
• грамм_uc⁻¹({‹A›, ‹bb›}) = {‹a›}, поскольку грамм_uc(‹A›) = ‹A›, а ‹bb› недоступен для грамм_uc.

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

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

Проекция струны

Если s это строка, а ${\displaystyle \Sigma }$ это алфавит, струнная проекция из s это строка, которая получается в результате удаления всех символов, которых нет в ${\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\}}$^{[нужна цитата ]}

Правое частное

В правое частное персонажа а из строки s усечение символа а в строке s, с правой стороны. Обозначается как ${\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 | ∃т∈L₂. ул∈L₁ }.^[7]Это не является обобщением приведенного выше определения, поскольку для строки s и отличные персонажи а, б, Из определения Хопкрофта и Ульмана следует {са} / {б} давая {}, а не {ε}.

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

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

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

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

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

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

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

Правильная отмена

В правильная отмена персонажа а из строки s это удаление первого появления символа а в строке 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. Zbl  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). «Производные от регулярных выражений». J ACM. 11 (4): 481–494. Дои:10.1145/321239.321249.