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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Чаще всего алфавит рассматривается как непустое конечное множество. Например, алфавит лежит в основе азбуки Морзе, алфавит  — общепринятый набор символов для представления информации в компьютерах. Нотные знаки, цифры — также примеры конечных алфавитов. В некоторых случаях рассматриваются и бесконечные алфавиты, например, множество натуральных чисел  — простейший пример счётного алфавита (при этом натуральные числа могут быть рассмотрены и как слова над конечным алфавитом цифр).

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