Jump to content

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

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

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

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

Строка — это конечная последовательность символов. строка Пустая обозначается .Объединение двух строк и обозначается , или короче на .Объединение с пустой строкой не имеет значения: .Объединение строк ассоциативно : .

Например, .

Язык это конечный или бесконечный набор строк.Помимо обычных операций над множествами, таких как объединение, пересечение и т. д., к языкам можно применять конкатенацию:если оба и это языки, их конкатенация определяется как набор конкатенаций любой строки из и любая строка из , формально .И снова точка конкатенации часто опускается для краткости.

Язык состоящий только из пустой строки, следует отличать от пустого языка .Объединение любого языка с первым не вносит никаких изменений: ,в то время как объединение с последним всегда дает пустой язык: .Объединение языков ассоциативно: .

Например, сокращая , набор всех трехзначных десятичных чисел получается как . Набор всех десятичных чисел произвольной длины является примером бесконечного языка.

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

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

Алфавит строки — это набор всех символов, встречающихся в конкретной строке. Если 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 , начиная с правой части. Он обозначается как и рекурсивно определяется как

Пустую строку всегда можно отменить:

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

[ нужна ссылка ]

Префиксы

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

Префиксы строки — это набор всех префиксов строки относительно данного языка:

где .

Префиксное языка закрытие

Пример:

Язык называется префиксно-закрытым, если .

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

Префиксное отношение является бинарным отношением такой, что тогда и только тогда, когда . Это отношение является частным примером префиксного порядка . [ нужна ссылка ]

См. также

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

Примечания

[ редактировать ]
  1. ^ Хотя каждый регулярный язык также является контекстно-свободным, предыдущая теорема не подразумевается текущей, поскольку первая дает формирующий результат для регулярных языков.
  2. ^ Строго формально гомоморфизм дает язык, состоящий всего из одной строки, т.е. .
  3. ^ Это следует из упомянутого выше замыкания при произвольных заменах.
  • Хопкрофт, Джон Э.; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Ридинг, Массачусетс: Издательство Addison-Wesley. ISBN  978-0-201-02988-8 . Збл   0426.68001 . (См. главу 3.)
  1. ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60
  2. ^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.4, стр.60
  3. ^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.2, стр. 131
  4. ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.60-61.
  5. ^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.5, стр.61
  6. ^ Хопкрофт, Ульман (1979), раздел 6.2, теорема 6.3, стр. 132
  7. ^ Хопкрофт, Ульман (1979), раздел 3.2, стр.62
  8. ^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID   14126942 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3c79b0f6ce722181ebdfa8d9ac0a09bb__1718661720
URL1:https://arc.ask3.ru/arc/aa/3c/bb/3c79b0f6ce722181ebdfa8d9ac0a09bb.html
Заголовок, (Title) документа по адресу, URL1:
String operations - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)