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

редактировать

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

Содержание

1 Строки и языки
2 алфавит строки
3 Подстановка строк
4 Гомоморфизм струны
5 Проекция струны
6 Правое частное
7 Синтаксическое отношение
8 Правильная отмена
9 префиксов
10 См. Также
11 Примечания
12 Ссылки

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

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

Язык, состоящий только из пустой строки, следует отличать от пустого языка. Конкатенация любой язык с бывшим не делает каких - либо изменений:, в то время как конкатенация с последним всегда дает пустой язык:. Стечение языков ассоциативно. ${\ Displaystyle \ {\ varepsilon \}}$ $\ {\ varepsilon \}$ ${\ Displaystyle \ {\}}$ $\ {\}$ ${\ Displaystyle S \ cdot \ {\ varepsilon \} = S = \ {\ varepsilon \} \ cdot S}$ $S \ cdot \ {\ varepsilon \} = S = \ {\ varepsilon \} \ cdot S$ ${\ Displaystyle S \ cdot \ {\} = \ {\} = \ {\} \ cdot S}$ $S \ cdot \ {\} = \ {\} = \ {\} \ cdot S$ ${\ Displaystyle S \ CDOT (Т \ CDOT U) = (S \ CDOT T) \ CDOT U}$ $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 \}}$ $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}$ $D \ cdot D \ cdot D$

Алфавит строки

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

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

\ operatorname {Alph} (s)

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

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

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

Пусть L - язык, а Σ - его алфавит. Строка подстановки или просто подмена отображение F, которая отображает символы Е на языках (возможно, в другом алфавите). Так, например, для символа a ∈ Σ имеем f ( a) = L a, где L a ⊆ ∆ ^* - некоторый язык с алфавитом ∆. Это отображение может быть расширено до строк как

f (ε) = ε

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

f ( sa) = f ( s) f ( а)

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

{\ Displaystyle е (L) = \ bigcup _ {s \ in L} f (s)}

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

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

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

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

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

f uc (‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
f uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›} и
f uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

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

f uc ({‹Straße›, ‹u2›, ‹Go!›}) = {‹STRASSE›} ∪ {‹U›} ∪ {} = {‹STRASSE›, ‹U›}.

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

Струна гомоморфизм (часто называют просто как гомоморфизм в теории формальных языков ) является строкой замещения, так что каждый символ заменяется одной строкой. То есть, где - строка для каждого символа. ${\ Displaystyle f (а) = s}$ ${\ Displaystyle f (а) = s}$ ${\ displaystyle s}$ $s$ ${\ displaystyle a}$ $а$

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

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

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

${\ Displaystyle е ^ {- 1} (L) = \ {s | f (s) \ in L \}}$ ${\ Displaystyle е ^ {- 1} (L) = \ {s | f (s) \ in L \}}$

В общем, пока есть ${\ Displaystyle е (е ^ {- 1} (L)) \ neq L}$ ${\ Displaystyle е (е ^ {- 1} (L)) \ neq L}$

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

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

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

Класс регулярных языков замкнут относительно гомоморфизмов и обратных гомоморфизмов. Точно так же контекстно-свободные языки замкнуты относительно гомоморфизмов и обратных гомоморфизмов.

Гомоморфизм строк называется ε-свободным (или e-свободным), если для всех a в алфавите. Простые однобуквенные шифры подстановки являются примерами (ε-свободных) гомоморфизмов строк. ${\ Displaystyle е (а) \ neq \ varepsilon}$ ${\ Displaystyle е (а) \ 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 не является ε-свободным, поскольку он отображает eg ‹0› в ε.

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

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

Если s это строка, и является алфавитом, то строка проекция из S является строкой, что результаты, удалив все символы, которые не являются в. Он записывается как. Формально это определяется удалением символов с правой стороны: ${\ displaystyle \ Sigma}$ $\Сигма$ ${\ displaystyle \ Sigma}$ $\Сигма$ ${\ Displaystyle \ pi _ {\ Sigma} (s) \,}$ $\ pi _ {\ Sigma} (s) \,$

{\ displaystyle \ pi _ {\ Sigma} (s) = {\ begin {cases} \ varepsilon amp; {\ t_dv {if}} s = \ varepsilon {\ t_dv {пустая строка}} \\\ pi _ {\ Sigma} (t) amp; {\ t_dv {if}} s = ta {\ t_dv {and}} a \ notin \ Sigma \\\ pi _ {\ Sigma} (t) a amp; {\ t_dv {if}} s = та {\ t_dv {и}} а \ in \ Sigma \ end {case}}}

\ pi _ {\ Sigma} (s) = {\ begin {cases} \ varepsilon amp; {\ t_dv {if}} s = \ varepsilon {\ t_dv {пустая строка}} \\\ pi _ {\ Sigma} ( t) amp; {\ t_dv {if}} s = ta {\ t_dv {and}} a \ notin \ Sigma \\\ pi _ {\ Sigma} (t) a amp; {\ t_dv {if}} s = ta {\ t_dv {и}} а \ in \ Sigma \ end {case}}

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

Строковую проекцию можно превратить в проекцию языка. Для формального языка L его проекция дается формулой

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

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

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

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

{\ displaystyle (sa) / b = {\ begin {case} s amp; {\ t_dv {if}} a = b \\\ varepsilon amp; {\ t_dv {if}} a \ neq b \ end {cases}}}

(sa) / b = {\ begin {case} s amp; {\ t_dv {if}} a = b \\\ varepsilon amp; {\ t_dv {if}} a \ neq b \ end {cases}}

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

{\ Displaystyle \ varepsilon / а = \ varepsilon}

\ varepsilon / a = \ varepsilon

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

{\ Displaystyle S / a = \ {s \ in M ​​\ \ vert \ sa \ in S \}}

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

Аналогично можно определить левые частные, при этом операции выполняются слева от строки.

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

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

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

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

{\ Displaystyle \ sim _ {S} \; \, = \, \ {(s, t) \ в M \ times M \ \ vert \ S / s = S / t \}}

\ 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}$ $s \ div a$

{\ displaystyle (sa) \ div b = {\ begin {case} s amp; {\ t_dv {if}} a = b \\ (s \ div b) a amp; {\ t_dv {if}} a \ neq b \ end { case}}}

(sa) \ div b = {\ begin {case} s amp; {\ t_dv {if}} a = b \\ (s \ div b) a amp; {\ t_dv {if}} a \ neq b \ end {cases}}

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

{\ Displaystyle \ varepsilon \ div a = \ varepsilon}

\ varepsilon \ div a = \ varepsilon

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

{\ Displaystyle \ pi _ {\ Sigma} (s) \ div a = \ pi _ {\ Sigma} (s \ div a)}

\ pi _ {\ Sigma} (s) \ div a = \ pi _ {\ Sigma} (s \ div a)

Префиксы

В префиксов строки есть множество всех префиксов в строке, в отношении данного языка:

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

\ operatorname {Pref} _ {L} (s) = \ {t \ \ vert \ s = tu {\ t_dv {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, и \ in \ operatorname {Альф} (L) ^ {*} \ right \}}

\ 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 \} {\ t_dv {then}} \ operatorname {Pref} (L) = \ left \ {\ varepsilon, a, ab, abc \ right \}}$ $L = \ left \ {abc \ right \} {\ t_dv {then}} \ operatorname {Pref} (L) = \ left \ {\ varepsilon, a, ab, abc \ right \}$

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

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

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

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

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

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

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

Ноты

Ссылки

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