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

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

Строки , также известные как «слова» или «предложения», в алфавите определяются как последовательность символов из набора алфавита. ^{[ 4 ]} Например, алфавит строчных букв от «а» до «z» может использоваться для образования английских слов, таких как «айсберг», в то время как алфавит как прописных, так и строчных букв также может использоваться для образования имен собственных, таких как «Arc.Ask3.Ru». Распространенным алфавитом является {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, _ }.

Учитывая алфавит $\Sigma$ , набор всех строк длины $n$ над алфавитом $\Sigma$ обозначается $\Sigma ^{n}$ . Набор ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ всех конечных строк (независимо от их длины) обозначается звездным оператором Клини как $\Sigma ^{*}$ , и также называется замыканием Клини $\Sigma$ . Обозначения $\Sigma ^{\omega }$ указывает набор всех бесконечных последовательностей в алфавите $\Sigma$ , и $\Sigma ^{\infty }$ указывает на набор $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ всех конечных или бесконечных последовательностей.

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

Приложения

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

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

См. также

Ссылки

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

Литература

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

[1] Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . PWS-Кент. п. 114. ИСБН 0-53492-373-9 . Алфавит — это непустое конечное множество , члены которого называются символами или знаками .

[Ebbinghaus1994-2] Эббингауз, Х.-Д. ; Флум, Дж.; Томас, В. (1994). Математическая логика (2-е изд.). Нью-Йорк : Спрингер . п. 11. ISBN 0-387-94258-0 . По алфавиту ${\mathcal {A}}$ мы имеем в виду непустой набор символов .

[Rosen-3] Розен, Кеннет Х. «Дискретная математика и ее приложения, седьмое издание» McGraw-Hill 2012. Страницы 847-851. Со страницы 849: «Словарь (или алфавит) V — это конечный непустой набор элементов, называемых символами. Слово (или предложение) над V — это строка конечной длины элементов V».

[Rautenberg-4] Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (PDF) (Третье изд.). Спрингер. п. хх. ISBN 978-1-4419-1220-6 . Если 𝗔 — алфавит , т. е. если элементы 𝐬 ∈ 𝗔 являются символами или хотя бы именованными символами, то последовательность (𝐬 ₁ ,...,𝐬 _n )ε𝗔 ^н записывается как 𝐬 ₁ ···𝐬 _n и называется строкой или словом над 𝗔.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]