Строковые операции
В информатике , в области теории формального языка , часто используются различные строковые функции ; однако используемые обозначения отличаются от тех, которые используются для компьютерного программирования , а некоторые часто используемые в теоретической области функции редко используются при программировании. В этой статье даны определения некоторых из этих основных терминов.
Строки и языки
[ редактировать ]Строка — это конечная последовательность символов. строка Пустая обозначается .Объединение двух строк и обозначается , или короче на .Объединение с пустой строкой не имеет значения: .Объединение строк ассоциативно : .
Например, .
Язык — это конечный или бесконечный набор строк.Помимо обычных операций над множествами, таких как объединение, пересечение и т. д., к языкам можно применять конкатенацию:если оба и это языки, их конкатенация определяется как набор конкатенаций любой строки из и любая строка из , формально .И снова точка конкатенации часто опускается для краткости.
Язык состоящий только из пустой строки, следует отличать от пустого языка .Объединение любого языка с первым не вносит никаких изменений: ,в то время как объединение с последним всегда дает пустой язык: .Объединение языков ассоциативно: .
Например, сокращая , набор всех трехзначных десятичных чисел получается как . Набор всех десятичных чисел произвольной длины является примером бесконечного языка.
Алфавит строки
[ редактировать ]Алфавит строки — это набор всех символов, встречающихся в конкретной строке. Если s — строка, ее алфавит обозначается
Алфавит языка это набор всех символов, которые встречаются в любой строке , формально: .
Например, набор это алфавит строки ,и вышеизложенное это алфавит вышеуказанного языка а также языка всех десятичных чисел.
Замена строки
[ редактировать ]Пусть L — язык , и пусть Σ — его алфавит. Подстановка строк или просто замена — это отображение f , которое отображает символы из Σ в языки (возможно, в другом алфавите). Так, например, для характера a ∈ Σ имеем f ( a ) = L a, где L a ⊆ ∆ * — некоторый язык, алфавит которого равен Δ. Это отображение может быть расширено на строки как
- е (е)=е
для пустой строки ε и
- ж ( са ) = ж ( s ) ж ( а )
для строки s ∈ L и символа a ∈ Σ. Замены строк могут быть распространены на целые языки как [1]
Обычные языки закрыты при подстановке строк. То есть, если каждый символ в алфавите обычного языка заменить другим регулярным языком, результатом по-прежнему будет регулярный язык. [2] Аналогично, контекстно-свободные языки закрыты при подстановке строк. [3] [примечание 1]
Простым примером является преобразование f uc (.) в верхний регистр, которое можно определить, например, следующим образом:
характер | сопоставлен с языком | замечание |
---|---|---|
х | еба ук ( х ) | |
‹ а › | { ‹ А › } | сопоставить символ нижнего регистра с соответствующим символом верхнего регистра |
‹ А › | { ‹ А › } | сопоставить прописные символы с самим собой |
SS < > | { < SS > } | нет символов в верхнем регистре, отображается строка из двух символов |
‹0› | { е } | сопоставить цифру с пустой строкой |
‹!› | { } | запретить знаки препинания, сопоставить пустой язык |
... | аналогично для других персонажей |
Для расширения fuc , на строки мы имеем, например
- f uc (‹Street›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹ДОРОГА›},
- f uc (‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, и
- f uc (‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.
Для распространения fuc , на языки мы имеем, например
- f uc ({ ‹Штрассе›, ‹u2›, ‹Go!› }) = { ‹ШТРАССЕ› } ∪ { ‹U› } ∪ { } = { ‹ШТРАССЕ›, ‹U› }.
Струнный гомоморфизм
[ редактировать ]Строковый гомоморфизм (часто называемый просто гомоморфизмом в теории формального языка ) — это строковая замена, при которой каждый символ заменяется одной строкой. То есть, , где это строка для каждого символа . [примечание 2] [4]
Строковые гомоморфизмы — это моноидные морфизмы на свободном моноиде , сохраняющие пустую строку и бинарную операцию конкатенации строк . Учитывая язык , набор называется гомоморфным образом . Обратный гомоморфный образ строки определяется как
а обратный гомоморфный образ языка определяется как
В общем, , хотя у человека есть
и
для любого языка .
Класс регулярных языков замкнут относительно гомоморфизмов и обратных гомоморфизмов. [5] Аналогично, контекстно-свободные языки замкнуты относительно гомоморфизмов [примечание 3] и обратные гомоморфизмы. [6]
Строковый гомоморфизм называется ε-свободным (или e-свободным), если для всех а в алфавите . Простые однобуквенные шифры замены являются примерами (ε-свободных) гомоморфизмов строк.
Пример гомоморфизма строк g uc также можно получить, задав аналогичную вышеописанной замену : g uc (‹a›) = ‹A›, ..., g uc (‹0›) = ε, но положив g uc неопределённым о знаках препинания. Примеры обратных гомоморфных изображений:
- г ук −1 ({ ‹SSS› }) = { ‹sss›, ‹ss›, ‹ßs› }, так как g uc (‹sss›) = g uc (‹ss›) = g uc (‹ßs›) = ‹SSS› , и
- г ук −1 ({ ‹A›, ‹bb› }) = { ‹a› }, так как g uc (‹a›) = ‹A›, а ‹bb› не может быть достигнуто с помощью g uc .
Для последнего языка g uc ( g uc −1 ({ ‹A›, ‹bb› })) = g uc ({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }.Гомоморфизм g uc не является ε-свободным, поскольку он отображает, например, ‹0› в ε.
Очень простой пример гомоморфизма строк, который отображает каждый символ только в символ, — это преобразование строки в кодировке EBCDIC в ASCII .
Струнная проекция
[ редактировать ]Если s — строка и — это алфавит, строковая проекция s — это строка, полученная в результате удаления всех символов, отсутствующих в . Это написано как . Формально это определяется удалением символов из правой части:
Здесь обозначает пустую строку . Проекция строки по существу аналогична проекции в реляционной алгебре .
Проекцию строки можно превратить в проекцию языка . Учитывая формальный язык L , его проекция задается формулой
- [ нужна ссылка ]
Правое и левое частное
[ редактировать ]Правое частное символа a из строки s — это усечение символа a в строке s с правой стороны. Он обозначается как . Если строка не имеет справа , результатом будет пустая строка. Таким образом:
Частное пустой строки может быть взято:
Аналогично, учитывая подмножество моноида , можно определить факторподмножество как
Левые частные могут быть определены аналогичным образом, при этом операции выполняются слева от строки. [ нужна ссылка ]
Хопкрофт и Ульман (1979) определяют фактор L 1 / L 2 языков L 1 и L 2 по одному и тому же алфавиту как L 1 / L 2 = { s | ∃ т ∈ L 2 . ст ∈ L 1 } . [7] Это не обобщение приведенного выше определения, поскольку для строки s и различных символов a , b определение Хопкрофта и Ульмана подразумевает получение {}, а не {ε}.
Левое частное (когда оно определено аналогично Хопкрофту и Ульману, 1979) одноэлементного языка L 1 и произвольного языка L 2 известно как производная Бжозовского ; если L 2 представлен регулярным выражением , то же самое может быть и левым частным. [8]
Синтаксическое отношение
[ редактировать ]Правильное частное подмножества моноида определяет отношение эквивалентности , правым отношением S. синтаксическим называемое Это дано
Очевидно, что отношение имеет конечный индекс (имеет конечное число классов эквивалентности) тогда и только тогда, когда правые факторы семейства конечны; то есть, если
конечно. В случае, когда M — моноид слов в некотором алфавите, S — регулярный язык , то есть язык, который может распознаваться конечным автоматом . Подробнее об этом говорится в статье о синтаксических моноидах . [ нужна ссылка ]
Право отмены
[ редактировать ]Правое удаление символа a из строки s — это удаление первого вхождения символа a в строку s , начиная с правой части. Он обозначается как и рекурсивно определяется как
Пустую строку всегда можно отменить:
Очевидно, что правильная отмена и проекция коммутируют :
- [ нужна ссылка ]
Префиксы
[ редактировать ]Префиксы строки — это набор всех префиксов строки относительно данного языка:
где .
Префиксное языка закрытие
Пример:
Язык называется префиксно-закрытым, если .
Оператор закрытия префикса идемпотентен :
Префиксное отношение является бинарным отношением такой, что тогда и только тогда, когда . Это отношение является частным примером префиксного порядка . [ нужна ссылка ]
См. также
[ редактировать ]- Сравнение языков программирования (строковые функции)
- Лемма Леви
- Строка (информатика) — определение и реализация более простых операций со строками.
Примечания
[ редактировать ]- ^ Хотя каждый регулярный язык также является контекстно-свободным, предыдущая теорема не подразумевается текущей, поскольку первая дает формирующий результат для регулярных языков.
- ^ Строго формально гомоморфизм дает язык, состоящий всего из одной строки, т.е. .
- ^ Это следует из упомянутого выше замыкания при произвольных заменах.
Ссылки
[ редактировать ]- Хопкрофт, Джон Э.; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Ридинг, Массачусетс: Издательство Addison-Wesley. ISBN 978-0-201-02988-8 . Збл 0426.68001 . (См. главу 3.)
- ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60
- ^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.4, стр.60
- ^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.2, стр. 131
- ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60-61.
- ^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.5, стр.61
- ^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.3, стр. 132
- ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.62
- ^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .