WikiDer > Строковые операции - Википедия

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

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

Строка - это конечная последовательность символов. пустой строкой обозначается ${ 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 к строкам у нас есть, например,

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

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

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

Примечания

Рекомендации

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