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

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

Строки , также известные как «слова» в алфавите, определяются как последовательность символов из набора. Например, алфавит из строчных букв от «a» до «z» может использоваться для образования английских слов, таких как «айсберг», в то время как алфавит из прописных и строчных букв также может использоваться для образования собственных имен, таких как «Википедия». Обычный алфавит - это {0,1}, двоичный алфавит , а «00101111» является примером двоичной строки . Можно также рассмотреть бесконечную последовательность символов.

Для практических целей часто бывает необходимо ограничить символы в алфавите, чтобы они были однозначными при интерпретации. Например, если двухчленный алфавит равен {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 ^ {п}}$${\ textstyle \ bigcup _ {я \ in \ mathbb {N}} \ Sigma ^ {i}}$${\ Displaystyle \ Sigma ^ {*}}$${\ displaystyle \ Sigma}$${\ Displaystyle \ Sigma ^ {\ omega}}$${\ displaystyle \ Sigma}$${\ Displaystyle \ Sigma ^ {\ infty}}$${\ Displaystyle \ Sigma ^ {\ ast} \ чашка \ Sigma ^ {\ omega}}$

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

Приложения

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

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

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

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

использованная литература

Литература

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