В информатике , в области теории формального языка , часто используются различные строковые функции ; однако используемые обозначения отличаются от обозначений, используемых для компьютерного программирования , и некоторые часто используемые функции в теоретической области редко используются при программировании. В этой статье дается определение некоторых из этих основных терминов.
Строки и языки
Строка - это конечная последовательность символов. Пустая строка обозначается. Конкатенация двух строк а также обозначается , или короче на . Конкатенация с пустой строкой не имеет значения:. Объединение строк ассоциативно :.
Например, .
Язык является конечным или бесконечным множеством строк. Помимо обычных операций над множествами, таких как объединение, пересечение и т. Д., Конкатенация может применяться к языкам: если оба а также языки, их конкатенация определяется как набор конкатенаций любой строки из и любая строка из , формально . Снова точка конкатенации часто опускается для краткости.
Язык состоящий только из пустой строки, следует отличать от пустого языка . Объединение любого языка с первым не вносит никаких изменений:, а конкатенация с последним всегда дает пустой язык: . Объединение языков ассоциативно:.
Например, сокращение , набор всех трехзначных десятичных чисел получается как . Набор всех десятичных чисел произвольной длины является примером бесконечного языка.
Алфавит строки
Алфавит строки является набором всех символов , которые происходят в определенной последовательности. Если s - строка, ее алфавит обозначается как
Алфавит языка это набор всех символов, которые встречаются в любой строке , формально: .
Например, набор это алфавит строки , и выше это алфавит указанного выше языка а также языка всех десятичных чисел.
Подстановка строк
Пусть L - язык , а Σ - его алфавит. Строка подстановки или просто подмена отображение F , которая отображает символы Е на языках (возможно , в другом алфавите). Так, например, для символа a ∈ Σ имеем f ( a ) = L a, где L a ⊆ ∆ * - некоторый язык с алфавитом ∆. Это отображение может быть расширено до строк как
- f (ε) = ε
для пустой строки ε и
- f ( sa ) = f ( s ) f ( а )
для строки s ∈ L и символа a ∈ Σ. Подстановки строк могут быть распространены на целые языки как [1]
Обычные языки закрываются при подстановке строк. То есть, если каждый символ в алфавите обычного языка заменяется другим обычным языком, результатом все равно будет обычный язык. [2] Точно так же контекстно-свободные языки закрываются при подстановке строк. [3] [примечание 1]
Простым примером является преобразование f uc (.) В верхний регистр, которое может быть определено, например, следующим образом:
персонаж | сопоставлен с языком | замечание |
---|---|---|
Икс | f uc ( x ) | |
< > | {< >} | сопоставить символ нижнего регистра с соответствующим символом верхнего регистра |
< > | {< >} | сопоставить заглавные буквы себе |
‹ 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›}.
Гомоморфизм струн
Струна гомоморфизм (часто называют просто как гомоморфизм в теории формальных языков ) является строкой замещения , так что каждый символ заменяется одной строкой. Это,, где это строка для каждого символа . [примечание 2] [4]
Струнные гомоморфизмы моноид морфизмов на свободном моноиде , сохраняющие пустую строку и бинарную операцию в конкатенации . Учитывая язык, набор называется гомоморфным из. Обратный гомоморфным строки определяется как
а обратный гомоморфный образ языка определяется как
В общем, , а у одного есть
а также
для любого языка .
Класс регулярных языков замкнут относительно гомоморфизмов и обратных гомоморфизмов. [5] Аналогично контекстно-свободные языки замкнуты относительно гомоморфизмов [примечание 3] и обратных гомоморфизмов. [6]
Гомоморфизм струны называется ε-свободным (или e-свободным), если для всех а в алфавите. Простые однобуквенные шифры подстановки являются примерами (ε-свободных) гомоморфизмов строк.
Пример строкового гомоморфизма g uc также можно получить, задав аналогично приведенной выше замене: g uc (‹a›) = ‹A›, ..., g uc (‹0›) = ε, но оставив g uc неопределенным. по знакам препинания. Примеры обратных гомоморфных образов:
- g uc −1 ({‹SSS›}) = {‹sss›, ‹sß›, ‹ßs›}, поскольку g uc (‹sss›) = g uc (‹sß›) = g uc (‹ßs›) = ‹SSS› и
- g uc −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 не является ε-свободным, поскольку он отображает eg ‹0› в ε.
Очень простой пример гомоморфизма строк, который отображает каждый символ только на символ, - это преобразование строки в кодировке EBCDIC в ASCII .
Проекция струны
Если s - строка, иявляется алфавитом, то строка проекция из S является строкой , что результаты, удалив все символы, которые не являются в. Он записывается как. Формально это определяется удалением символов с правой стороны:
Здесь обозначает пустую строку . Проекция строки по сути такая же, как в реляционной алгебре .
Строковую проекцию можно превратить в проекцию языка . Для формального языка L его проекция дается формулой
- [ необходима цитата ]
Правое частное
Правый фактор символа а из строки s является усечение символа а в строке s , с правой стороны. Обозначается как. Если строка не имеет на правой стороне, то результат будет пустая строка. Таким образом:
Можно взять частное от пустой строки:
Аналогично, учитывая подмножество моноида , можно определить частное подмножество как
Аналогично можно определить левые частные, при этом операции выполняются слева от строки. [ необходима цитата ]
Хопкрофт и Ульман (1979) определяют фактор L 1 / L 2 языков L 1 и L 2 по тому же алфавиту как L 1 / L 2 = { s | ∃ t ∈ L 2 . st ∈ L 1 }. [7] Это не является обобщением вышеприведенного определения, поскольку для строки s и различных символов a , b определение Хопкрофта и Ульмана подразумевает { sa } / { b }, дающее {}, а не {ε}.
Левое частное (определенное аналогично Хопкрофту и Ульману, 1979) одноэлементного языка L 1 и произвольного языка L 2 известно как производная Бжозовского ; если L 2 представлен регулярным выражением , то может быть и левое частное. [8]
Синтаксическое отношение
Правое частное подмножества моноида определяет отношение эквивалентности , называемое правое синтаксическое соотношением из S . Это дается
Очевидно, что отношение имеет конечный индекс (имеет конечное число классов эквивалентности) тогда и только тогда, когда правые частные семейства конечны; то есть, если
конечно. В случае, если M - моноид слов в некотором алфавите, тогда S является регулярным языком , то есть языком, который может быть распознан конечным автоматом . Более подробно это обсуждается в статье о синтаксических моноидах . [ необходима цитата ]
Правильная отмена
Право отмены символа а из строки s является удаление первого вхождения символа а в строке s , начиная с правой стороны. Обозначается как и рекурсивно определяется как
Пустая строка всегда может быть отменена:
Понятно, что правая отмена и проецирование сменяют друг друга :
- [ необходима цитата ]
Префиксы
В префиксов строки есть множество всех префиксов в строке, в отношении данного языка:
где .
Закрытия префикс языка является
Пример:
Язык называется префиксом закрытым, если.
Оператор замыкания префикса идемпотентен :
Префикс соотношение является бинарным отношением такой, что если и только если . Это отношение является частным примером порядка префиксов . [ необходима цитата ]
Смотрите также
- Сравнение языков программирования (строковые функции)
- Лемма Леви
- Строка (информатика) - определение и выполнение более основных операций со строками
Заметки
- ^ Хотя каждый регулярный язык также является контекстно-независимым, предыдущая теорема не подразумевается текущей теоремой, поскольку первая дает результат формирования для обычных языков.
- ^ Строго формально гомоморфизм порождает язык, состоящий только из одной строки, т. Е..
- ^ Это следует из упомянутого выше замыкания при произвольных подстановках.
Рекомендации
- Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления . Ридинг, Массачусетс: издательство Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001 . (См. Главу 3.)
- ^ Hopcroft Ульмана (1979), Sect.3.2, с.60
- ^ Hopcroft Ульмана (1979), Sect.3.2, теорема 3.4, с.60
- ^ Hopcroft Ульмана (1979), Sect.6.2, теорема 6.2, с.131
- ^ Hopcroft Ульмана (1979), Sect.3.2, p.60-61
- ^ Хопкрофт, Ульман (1979), раздел 3.2, теорема 3.5, стр.61
- ^ Hopcroft Ульмана (1979), Sect.6.2, теорема 6.3, с.132
- ^ Hopcroft Ульмана (1979), Sect.3.2, с.62
- ^ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM . 11 (4): 481–494. DOI : 10.1145 / 321239.321249 .