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

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

Строки и языки [ править ]

Строка - это конечная последовательность символов. Пустая строка обозначается . Объединение двух строк и обозначается или короче . Конкатенация с пустой строкой не имеет никакого значения: . Конкатенация строк является ассоциативной : .${\ 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 ( а )

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

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

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

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

Для расширения 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›}.

Гомоморфизм строк [ править ]

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

Струнные гомоморфизмы моноид морфизмов на свободном моноиде , сохраняющие пустую строку и бинарную операцию в конкатенации . С учетом языка , набор называется гомоморфное изображение из . Обратный гомоморфная строка определяются как${\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-свободным), если для всех 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 не является ε-свободным, поскольку он отображает eg ‹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\}}$^{[ необходима цитата ]}

Правое частное [ править ]

Правый фактор символа а из строки 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 | ∃ t ∈ L ₂ . st ∈ L ₁ }. ^[7] Это не является обобщением приведенного выше определения, поскольку для строки s и различных символов a , b определение Хопкрофта и Ульмана подразумевает { sa } / { 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 является регулярным языком , то есть языком, который может быть распознан конечным автоматом . Более подробно это обсуждается в статье о синтаксических моноидах . ^{[ необходима цитата ]}

Право отмена [ править ]

Право отмены символа а из строки 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)}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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