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

Алфави́т формального языка — множество атомарных (неделимых) символов какого-либо формального языка (иногда их называют буквами по аналогии с алфавитами естественных языков или символами). Из символов алфавита формального языка строятся слова, а заданием формальной грамматики — допустимые выражения языка.

Чаще всего алфавит рассматривается как непустое конечное множество. Например, алфавит $\text{[math]}$ $\text{[math]}$ $\{\cdot ,-\}$ $\{\cdot ,-\}$ лежит в основе азбуки Морзе, алфавит $\text{[math]}$ $\text{[math]}$ $\{0,1\}$ $\{0,1\}$ — общепринятый набор символов для представления информации в компьютерах. Нотные знаки, цифры — также примеры конечных алфавитов. В некоторых случаях рассматриваются и бесконечные алфавиты, например, множество натуральных чисел $\text{[math]}$ $\text{[math]}$ $\mathbb {N}$ $\mathbb {N}$ — простейший пример счётного алфавита (при этом натуральные числа могут быть рассмотрены и как слова над конечным алфавитом цифр).

Понятие алфавита формального языка широко применяется в лингвистике (в разделах, изучающих формальные грамматики), математической логике (прежде всего — теории моделей), теории автоматов, искусственном интеллекте (в том числе, в компьютерной лингвистике), информатике (в частности, в теории языков программирования). Отдельные теоретические проблемы построения слов и выражений формальных языков над алфавитами исследуются средствами общей алгебры и комбинаторики.