Строковые операции - Википедия - 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 (Т 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 о rangle }}$ это алфавит строки ${ Displaystyle langle какао rangle}$ , а над ${ displaystyle D}$ это алфавит над язык ${ Displaystyle D cdot D cdot D}$ а также языка всех десятичных чисел.

Подстановка строк

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

ж(ε) = ε

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

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

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

{ Displaystyle е (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 (а) = 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 е ^ {- 1} (L) = {s | f (s) in L }}$

В целом, ${ Displaystyle е (е ^ {- 1} (L)) neq L}$ , а у одного есть

${ Displaystyle е (е ^ {- 1} (L)) substeq L}$

и

${ Displaystyle L substeq е ^ {- 1} (е (L))}$

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

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

Гомоморфизм струны называется ε-свободным (или e-свободным), если ${ Displaystyle е (а) 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 {пустая строка}} pi _ { Sigma} (t) & { mbox {if}} s = ta { mbox {and}} a notin Sigma pi _ { Sigma} (t) a & { mbox {if}} s = та { mbox {и}} а in Sigma end {case}}}

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

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

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

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

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

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

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

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

{ Displaystyle varepsilon / а = varepsilon}

Аналогично, учитывая подмножество ${ Displaystyle S подмножество 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) в M times M vert S / s = S / t }}

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

{ Displaystyle {С / м верт м в М }}

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

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

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

{ displaystyle (sa) div b = { begin {case} s & { mbox {if}} a = b (s div b) a & { mbox {if}} a neq b end { случаи}}}

Пустая строка всегда может быть отменена:

{ 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)}$ . Это отношение является частным примером порядок префиксов.^{[нужна цитата ]}

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

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

Примечания

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