Алфавит (формальные языки)

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

В теории формального языка, строка определяется как конечная последовательность элементов базовой базы установить ; этот набор называется алфавитом строки или набора строк. Члены набора называются символами и обычно рассматриваются как представляющие буквы, символы или цифры. Например, общий алфавит - это {0,1}, двоичный алфавит и двоичная строка - это строка из алфавита {0,1}. Бесконечная последовательность букв также может быть построена из элементов алфавита.

Содержание

1 Обозначение
2 Приложения
3 См. Также
4 Ссылки
5 Литература

Обозначение

Если L - формальный язык, то есть ( возможно бесконечный) набор строк конечной длины, алфавит L - это набор всех символов, которые могут встречаться в любой строке в L. Например, если L - это набор всех идентификаторов переменных в языке программирования C алфавит L - это набор {a, b, c,..., x, y, z, A, B, C,..., X, Y, Z, 0, 1, 2,..., 7, 8, 9, _}.

Дан алфавит $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ , набор всех строк длиной $n {\ displaystyle n}$ $п$ на алфавит $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ обозначается как $Σ n {\ displaystyle \ Sigma ^ {n}}$ $\ Sigma ^ {n}$ . Множество $⋃ i ∈ N Σ i {\ textstyle \ bigcup _ {i \ in \ mathbb {N}} \ Sigma ^ {i}}$ ${\ textstyle \ bigcup _ {я \ in \ mathbb {N}} \ Sigma ^ {i}}$ всех конечных строк (независимо от их длины) обозначается оператором звезды Клини как $Σ ∗ {\ displaystyle \ Sigma ^ {*}}$ $\ Sigma ^ {*}$ , а также называется замыканием Клини $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ . Обозначение $Σ ω {\ displaystyle \ Sigma ^ {\ omega}}$ $\ Sigma ^ {\ omega}$ обозначает набор всех бесконечных последовательностей в алфавите $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ и $Σ ∞ {\ displaystyle \ Sigma ^ {\ infty}}$ $\ Sigma ^ {\ infty}$ обозначает набор $Σ ∗ ∪ Σ ω {\ displaystyle \ Sigma ^ {\ ast} \ cup \ Sigma ^ {\ omega}}$ ${\ displaystyle \ Sigma ^ {\ ast} \ cup \ Sigma ^ {\ omega}}$ всех конечных или бесконечных последовательностей.

Например, при использовании двоичного алфавита {0,1} строки ε, 0, 1, 00, 01, 10, 11, 000 и т. Д. Все находятся в замкнутом алфавите Клини (где ε представляет собой пустую строку ).

Приложения

Алфавиты важны при использовании формальных языков, автоматов и полуавтоматов. В большинстве случаев для определения экземпляров автоматов, таких как детерминированные конечные автоматы (DFA), требуется указать алфавит, из которого строятся входные строки для автомата. В этих приложениях обычно требуется, чтобы алфавит был конечным множеством, но не ограничивается иным образом.

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

См. Также

Комбинаторика слов

Ссылки

Литература

Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X.