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

Базовый набор символов, с помощью которых формируется язык

В формальной теории языка алфавит , иногда называемый словарем , представляет собой непустой набор неделимых символов / знаков / глифов , ^[1] обычно считающийся представляющим буквы, знаки, цифры, фонемы или даже слова. ^[2] [ ^3] Алфавиты в этом техническом смысле набора используются в самых разных областях, включая логику, математику, информатику и лингвистику. Алфавит может иметь любую мощность («размер») и, в зависимости от его назначения, может быть конечным (например, алфавит букв «a» - «z»), счетным (например, ) или даже несчетным (например, ). ${\displaystyle \{v_{1},v_{2},\ldots \}}$ ${\displaystyle \{v_{x}:x\in \mathbb {R} \}}$

Строки , также известные как «слова» или «предложения», в алфавите определяются как последовательность символов из набора алфавита. ^[4] Например, алфавит из строчных букв «a» — «z» может использоваться для формирования английских слов, таких как «iceberg», в то время как алфавит из заглавных и строчных букв также может использоваться для формирования имен собственных, таких как «Wikipedia». Распространенным алфавитом является {0,1}, двоичный алфавит , а «00101111» является примером двоичной строки . Бесконечные последовательности символов также могут рассматриваться (см. язык Omega ).

Часто бывает необходимо в практических целях ограничить символы в алфавите, чтобы они были однозначными при интерпретации. Например, если двухэлементный алфавит — {00,0}, то строка, записанная на бумаге как «000», неоднозначна, поскольку неясно, является ли она последовательностью из трех символов «0», «00», за которым следует «0», или «0», за которым следует «00».

Обозначение

Если 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 }$ ${\displaystyle n}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{n}}$ ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\omega }}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\infty }}$ ${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$

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

Приложения

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

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

Смотрите также

• Комбинаторика слов
• Терминальные и нетерминальные символы

Ссылки

1. Флетчер, Питер; Хойл, Хьюз; Патти, К. Уэйн (1991). Основы дискретной математики. PWS-Kent. стр. 114. ISBN 0-53492-373-9Алфавит — это непустое конечное множество , элементы которого называются символами или знаками .
2. Эббингауз, Х.-Д .; Флум, Дж.; Томас, У. (1994). Математическая логика (2-е изд.). Нью-Йорк : Springer . С. 11. ISBN 0-387-94258-0Под алфавитом мы подразумеваем непустой набор символов . ${\displaystyle {\mathcal {A}}}$
3. Розен, Кеннет Х. (2012). Дискретная математика и ее приложения (PDF) (7-е изд.). Нью-Йорк: McGraw Hill . С. 847–851. ISBN 978-0-07-338309-5. Словарь (или алфавит) V — это конечное непустое множество элементов, называемых символами. Слово (или предложение) над V — это строка конечной длины элементов V.
4. Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (PDF) (Третье изд.). Springer. стр. xx. ISBN 978-1-4419-1220-6. Если 𝗔 — алфавит , т. е. если элементы 𝐬 ∈ 𝗔 являются символами или, по крайней мере, именованными символами, то последовательность (𝐬 ₁ ,...,𝐬 _n )∈𝗔 ⁿ записывается как 𝐬 ₁ ···𝐬 _n и называется строкой или словом над 𝗔.

Литература

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